337. House Robber III.md

337. House Robber III

思路

此题是198. House Robber的拓展，只是此时不是在一个数组上偷而是在二叉树上偷，限制依然是相邻节点不能全偷。

思路和198题也是差不多的。

思路一

首先就是最容易想到的思路，类似198题思路一的动归思路， 即当前的dp值取决于其左右子树的dp值，不过198采用的是自底向上的动归而此题要自顶向下，而且dp也不是数组而是一个hash。

思路二

思路一额外开辟了hash来记录已经计算过的结果避免重复计算，其实也可以不用开辟hash达到这个目的， 详见代码，需要注意的是代码中helepr的的参数l和r传入的是引用!

C++

思路一

class Solution {
private:
    unordered_map<TreeNode*, int>dp;
    int helper(TreeNode* root){
        if(!root) return 0;
        if(dp.count(root)) return dp[root];
        
        int res1 = helper(root -> left) + helper(root -> right); // 不偷root
        int res2 = root -> val; // 偷root
        if(root -> left) 
            res2 += helper(root -> left -> left) + helper(root -> left -> right);
        if(root -> right) 
            res2 += helper(root -> right -> left) + helper(root -> right -> right);
        
        res1 = max(res1, res2);
        dp[root] = res1;
        return res1;
        
    }
public:
    int rob(TreeNode* root) {
        return helper(root);
    }
};

思路二

class Solution {
public:
    int rob(TreeNode* root) {
        int l = 0, r = 0;
        return helper(root, l, r);
    }
    int helper(TreeNode* node, int &l, int &r) {
        if (!node) return 0;
        int ll = 0, lr = 0, rl = 0, rr = 0;
        l = helper(node->left, ll, lr);
        r = helper(node->right, rl, rr);
        // 因为传入的是引用, 所以此时ll, lr, rl, rr都已经更新为了正确的是而不是0
        return max(node->val + ll + lr + rl + rr, l + r);
    }
};