Description Link to heading

337.house-robber-iii

Solution Link to heading

Strictly speaking, the idea of this problem is different from 198.house-robber，213.house-robber-ii.

At first, what this problem need to traverse is tree, rather than an array. We need to compare selecting curent node with selecting left-child node and right-child node rather than current node. So, we should select postorder traversal.

And as a problem of binary tree, we consider recursion.

  • termination conditions of recursion
    • current node is null;
  • return value of recursion function
    • return an array dp of length 2, dp[0] denotes maximum amount when not stealing current node, dp[1] denotes maximum amount when stealing current node;
  • what this level of recursion does
    • calculate the amount val1 when stealing current node, val2 for not stealing current node, return {val2, val1}.

Code Link to heading 

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }
    // array of length 2，0：not stealing，1：stealing
    vector<int> robTree(TreeNode* cur) {
        if (cur == NULL) return vector<int>{0, 0};
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        // steal cur，not cur-left, cur->right
        int val1 = cur->val + left[0] + right[0];
        // not steal cur，get max(left, right)
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
};