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

• ``````/**
* 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;

}``````

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