Untitled
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); } };