C++ DP solution with state memorization


  • 0
    F
    
    class Solution {
    public:
        int rob(TreeNode* root) {
            unordered_map<TreeNode*, int> dict;
            return help(root, dict);
        }
        
        int help(TreeNode* root, unordered_map<TreeNode*, int>& dict) {
            if(root == NULL)  return 0;
            if(dict.find(root)!=dict.end())  return dict[root];
            int val = 0;
            if(root->left != NULL) {
                val += help(root->left->left, dict) + help(root->left->right, dict);
            }
            if(root->right != NULL) {
                val += help(root->right->left, dict) + help(root->right->right, dict);
            }
            val = max(val + root->val, help(root->left, dict) + help(root->right, dict));
            dict[root] = val;
            return val;
        }
    };

Log in to reply
 

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