Clear solution with concise explanation (in C++)


  • 0
    H
    class Solution {
    public:
        int rob(TreeNode* root) {
            pair<int, int> p = dp(root);
            return max(p.first, p.second);
        }
        
        pair<int, int> dp(TreeNode* root) {
            if (!root) return {0, 0};
            pair<int, int> left = dp(root->left), right = dp(root->right);
            int include = root->val + left.second + right.second;
            int exclude = max(left.first, left.second) + max(right.first, right.second);
            return {include, exclude};
        }
    };
    
    /**
     * dp[n] means max amount of money the theif can rob begin with root n,
     * include means max amount with robbing n, exclude means max amount without robbing n,
     * so we get:
     * dp[n] = max(include, exclude), in which:
     *  include = n + dp[n->left.exclude] + dp[n->right.exclude]
     *  exclude = dp[n->left] + dp[n->right]
     **/

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.