Description
Given a binary tree root, return the maximum sum of the integers that can be obtained given no two integers can be adjacent parent to child.
Constraints:
-
n ≤ 100,000wherenis the number of nodes inroot
Example 1
Input
root = [1, [4, [3, null, null], [2, null, null]], [5, null, null]]
Output
10
Explanation
We can pick 3, 2 and 5. Note if we picked 4, we wouldn't be able to pick 3 and 2 since they are adjacent.
Intuition
dfs + dp
Implementation
/**
* class Tree {
* public:
* int val;
* Tree *left;
* Tree *right;
* };
*/
pair<int, int> dfs(Tree* node) {
if (!node) return make_pair(0, 0);
auto [leftWith, leftWithout] = dfs(node->left);
auto [rightWith, rightWithout] = dfs(node->right);
int withRoot = leftWithout + rightWithout + node->val;
int withoutRoot = max(leftWith, leftWithout) + max(rightWith, rightWithout);
return make_pair(withRoot, withoutRoot);
}
int solve(Tree* root) {
auto [with, without] = dfs(root);
return max(with, without);
}
Time Complexity
- Time: O(n)
- Space: O(logn)
Top comments (0)