8 ms C solution, top down, using on the way memoisation.


  • 0
    A
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
     int max(int a,int b)
     {
         return (a>b?a:b);
     }
     struct node
     {
         int dd[2];
         struct node *left,*right;
     };
     int gans(struct TreeNode* root,int f,struct node **x)
     {
            if (root==NULL)
            return 0;
            int ret;
            if (*x!=NULL&&(*x)->dd[f]!=-1)
            {
                return (*x)->dd[f];
            }
            if (*x==NULL)
            {
                *x=(struct node *)malloc(sizeof(struct node ));
                (*x)->left=(*x)->right=NULL;
                (*x)->dd[0]=(*x)->dd[1]=-1;
            }
            if (f)
            {
                ret= max(root->val+gans(root->left,!f,&((*x)->left))+gans(root->right,!f,&((*x)->right)),gans(root->left,1,&((*x)->left))+gans(root->right,1,&((*x)->right)));
            }
            else 
            {
                ret= gans(root->left,!f,&((*x)->left))+gans(root->right,!f,&((*x)->right));
            }
           
            (*x)->dd[f]=ret;
            
            return ret;
     }
    int rob(struct TreeNode* root) {
        struct node *x=NULL;
        int p2=gans(root,1,&x);
        return p2;
        
    }

Log in to reply
 

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