Maximum Non-Adjacent Tree Sum

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,000 where n is the number of nodes in root

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)