490. Thief in the Tree
A night thief has found a village whose houses sit along a branching road system shaped like a binary tree, with the entrance house stored in root. Each house holds val coins. The houses share a single alarm wire: if the thief robs two houses that are directly connected, meaning a house and one of its children, the alarm goes off and the night is ruined.
Return the largest total number of coins the thief can collect without ever robbing two directly connected houses. Houses that are only grandparent and grandchild, or that live in different branches, may safely be robbed together. If root is empty the answer is 0.
Example 1
- Input:
- root = [8,5,6,7,null,null,9]
- Output:
- 24
- Explanation:
Robbing the root (8) together with its grandchildren 7 and 9 gives 8 + 7 + 9 = 24, which beats robbing 5 and 6 (11) or 7 and 9 alone (16).
Example 2
- Input:
- root = [4,10,3,null,2,7,null,null,1]
- Output:
- 18
- Explanation:
Robbing the node 10 along with 7 and 1 (none of which are directly connected) collects 18, the best possible.
Constraints
0 ≤ number of nodes ≤ 105
0 ≤ Node.val ≤ 104
The answer always fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)