64ms C++ DP solution


  • 0
    R

    basic idea is to compare the value with and without rob current node.

    class Solution {
    public:
        int rob(TreeNode* root) {
            unordered_map<TreeNode*, unordered_map<int, int>> dp;
            return max(getValue(root, true, dp), getValue(root, false, dp));
        }
    
        int getValue(TreeNode* root, bool canRob, unordered_map<TreeNode*, unordered_map<int, int>>& dp) {
            if (!root) return 0;
            if (dp[root][canRob]) return dp[root][canRob];
            if (canRob) {
                int notrob = getValue(root->left, canRob, dp) + getValue(root->right, canRob, dp);
                int robbed = root->val + getValue(root->left, !canRob, dp) + getValue(root->right, !canRob, dp);
                dp[root][canRob] = max(notrob, robbed);
                return dp[root][canRob];
            }
    
            dp[root][canRob] = getValue(root->left, !canRob, dp) + getValue(root->right, !canRob, dp);
            return dp[root][canRob];
        }
    };

Log in to reply
 

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