【题解】遍历二叉树

这道题一开始看到的时候想先把二叉树剪出来，然后再找出叶子节点做一个动态规划，然后仔细一想发现，对于满二叉树来说，中序遍历的第1，3，5，7.。。项就是叶子节点。

那我们就可以直接获得叶子节点了， 然后用 表示前 个节点可以获得的最大粮食数，可以从(偷当前节点的粮食)和(不偷当前节点的粮食)转移而来。

#include<iostream>

using namespace std;

const int MAXN = 1e5+10;
int main()
{
    int n;
    cin >> n;
    int t;
    for(int i = 0 ; i < n ; i++){cin >>t;}//忽略掉先序遍历
    int arr[MAXN];
    int dp[MAXN];
    for(int i = 0 ; i < n ; i++)//取中序遍历的第1，3，5，7位
    {
        if(i%2==0){cin>>arr[i/2];}
        else{cin>>t;}
    }
    dp[0] = arr[0];
    dp[1] = max(arr[0],arr[1]);
    for(int i = 2 ; i <= n/2 ; i++)//动态规划状态转移
    {
        dp[i] = max(dp[i-2]+arr[i],dp[i-1]);
    }
    cout<<dp[n/2];
    return 0;
}