New Idea ,cpp ,


  • 0
    E

    The comment section is the answer to my previous question,but TML ,because i use four recursion for every node,but the new slover(other's idea) just use two recursion , it store the grandchild value to simplify the question

    /**
     * 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;
            int l=0,r=0;
            return robber(root , l, r);
        }
        
        int robber(TreeNode* ty,int& l,int& r){
            if(ty==NULL)return 0;
            int ll=0;int lr=0;int rl=0;int rr=0;
            // int l1 = robber(1,ty->left),r1 = robber(1,ty->right),
            //     l0 = robber(0,ty->left),r0 = robber(0,ty->right);
            
            // if(t==1){
            //     return max(l1+r1,ty->val+l0+r0);    
            // }else{
            //     return l1+r1;
            // }
            
            l = robber(ty->left,ll,lr);
            r = robber(ty->right,rl,rr);
            return max( ty->val+ll+lr+rl+rr,l+r); 
        }
    };
    

Log in to reply
 

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