leetcode337

隔行二叉树问题
1.动态规划问题还是应该写一下公式。
2.这个题对我的难点之一在于，我固化的思维，完全想不到，刷题的方法可以返回两个值，或者需要返回两个值。
过去固化的思维没有想到的：
1）倒序时间可以用栈装一下（拓扑排序）
2）map存指针可以映射（链表复制）
3）树递归方法可以传入两个指针递归（对称二叉树）
4）树返回方法（或者其它动态规划方法），可以返回两个值！！！！

第一思路一定是dfs求解的方法，这个点在选的里面，这个点不在选的里面。
我想，这个点在，孩子节点一定不在——》得到一个结果。
这个点不在——》孩子节点可以在可以不在，得到结果。
两个结果选最大。
这样我传入一个flag代表这个点在不在。
但是这样每个点需要重复算两次，因为每个点两种情况，（2^n）时间复杂度。（比如我会想到维持状态是从参数传入，而不是返回值）

但是呢，其实如果每次返回在不在两种情况来着，每个节点只需要计算一次，也就是O(n)时间复杂度。
（这就是动态规划的秒处）

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

    3
   / \
  2   3
   \   \ 
    3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:

输入: [3,4,5,1,3,null,1]

    3
   / \
  4   5
 / \   \ 
1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> findmax(TreeNode* root){
        if(!root)
            return {0,0};
        if(!root->left&&!root->right){
            return {root->val,0};//一定在，一定不在
        }
        //一定不在
        vector<int> left=findmax(root->left);
        vector<int> right=findmax(root->right);
        int notismax = max(left[0],left[1])+max(right[0],right[1]);
        //一定在
        int ismax = left[1]+right[1]+root->val;
        return {ismax,notismax};
        
    }
    
    
    int rob(TreeNode* root) {
        vector<int> a=findmax(root);
        return max(a[0],a[1]);

    }
};

我第一种想法，传入flag的方法，和↓
https://blog.csdn.net/MMChinaMM/article/details/52411080
想法一样，（但是我思路还是有点混乱，但是基本是这样的）
↓这个博文也是
https://www.cnblogs.com/zhizhiyu/p/10221064.html

class Solution {
public:
    int rob(TreeNode* root) {
        return dfs(root, false);
    }
private:
    int dfs(TreeNode *t, bool flag) {
        if (!t)return 0;
        int tmp = dfs(t->left, false) + dfs(t->right, false);
        if (flag)
            return tmp;
        else return max(t->val + dfs(t->left, true) + dfs(t->right, true), tmp);
    }
};