Simple C++ solution, using dynamic programming


  • 0
    C
    class Solution {
    public:
        int rob(TreeNode* root) {
            if(!root) return 0;
            vector<int> dp = helper(root);
            int result = max(dp[0], dp[1]);
            return result;
        }
        vector<int> helper(TreeNode* root){
            vector<int> result(2, 0), left(2, 0), right(2, 0);
            if(root -> left) left = helper(root -> left);
            if(root -> right) right = helper(root -> right);
            
            result[0] = max(left[0], left[1]) + max(right[0], right[1]);
            result[1] = left[0] + right[0] + root -> val;
            return result;
        }
    };
    

Log in to reply
 

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