9ms C++ solution using DP


  • 0
    B

    using negative value to represent the max value of the root that has already been computed

     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        int rob(TreeNode* root) {
            if(root == NULL) return 0;
            if(root->val<0) return -root->val;
            if(root->left == NULL && root->right == NULL) return root->val;
            if(root->left == NULL) 
            {
                root->val = -max(rob(root->right->left)+rob(root->right->right)+root->val,rob(root->right));
                return -root->val;
            }
            if(root->right == NULL)
            {
                root->val = -max(rob(root->left),rob(root->left->left)+rob(root->left->right)+root->val);
                return -root->val;
                
            }
            root->val = -max(rob(root->left)+rob(root->right),rob(root->right->left)+rob(root->right->right)+rob(root->left->left)+rob(root->left->right)+root->val);
        
            return -root->val;
        }
    };```

Log in to reply
 

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