Untitled
unknown
plain_text
a year ago
1.0 kB
4
Indexable
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: pair<int,int> solve(TreeNode* root){ if(!root) return {0,0}; if(!root->left && !root->right){ return {root->val,0}; //included,excluded } pair<int,int>l=solve(root->left); pair<int,int>r=solve(root->right); int inc=root->val+l.second+r.second; int exc=max(l.first,l.second) +max(r.first,r.second); //if the current root isnt robbed we must choose the max of left and right valuse because they arent adjacent return {inc,exc}; } int rob(TreeNode* root) { pair<int,int> res=solve(root); return max(res.first,res.second); } };
Editor is loading...
Leave a Comment