hardTreesPure DSA~35 min
Maximum Value With No Two Adjacent Tree Nodes
Each node of a tree carries a value, but selecting a node forbids selecting its direct parent or children. Maximize the total value of the chosen nodes.
Problem
Given the root of a binary tree where each node holds a non-negative value, return the maximum sum of values you can collect such that no two chosen nodes are directly connected (parent-child).
Input
A binary tree root with integer node values.
Output
An integer: the maximum non-adjacent sum.
Constraints
- 1 <= number of nodes <= 10^4
- 0 <= node value <= 10^4
- The tree may be unbalanced.
Examples
Example 1
Input
root = [3,2,3,null,3,null,1]
Output
7
Pick the root (3) and the two grandchildren (3 + 1) for 7.
Example 2
Input
root = [3,4,5,1,3,null,1]
Output
9
Pick the children 4 and 5 for 9.