Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
871 B
0
Indexable
Never
class Solution{
  public:
    //Function to return the maximum sum of non-adjacent nodes.
    pair<int,int> drive(Node* root){  //(include value,exclude value)
        
        if(root==NULL) return make_pair(0,0);
        
        pair<int,int> left = drive(root->left);
        pair<int,int> right = drive(root->right);
        
        int  include= left.second+right.second+root->data; //if i include this node i cant
       //                                                      include its left  or right
       
        /*if i exclude this node then i take max of whatever is below me*/
        int exclude= max(right.second,right.first) +max(left.first,left.second);
        return make_pair(include,exclude);
        
        
    }
    int getMaxSum(Node *root) 
    {
        pair<int,int>  ans=drive(root);
        return max(ans.first,ans.second);

    }
};