House Robber III
The key idea
Each node returns two numbers: the best total if you rob this node (then its children must be skipped), and the best if you skip it (then each child is free to choose its own best). A parent combines its children's pairs in O(1), so one post-order pass solves the whole tree.
Problem
The thief has found a new neighborhood to rob. All the houses in this place form a binary tree rooted at root, where the only entrance is the root and every other house has exactly one parent house.
Each house stores some amount of money. The neighborhood has a security rule: the police are automatically alerted if two directly-connected houses are robbed on the same night. In tree terms, a robbed node and its parent cannot both be robbed.
Return the maximum amount of money the thief can rob without alerting the police.
Constraints
- The number of nodes in the tree is in the range
[1, 10^4]. 0 <= Node.val <= 10^4
Examples
Input: root = [3,2,3,null,3,null,1]
Output: 7
Input: root = [3,4,5,1,3,null,1]
Output: 9
Complexity
Time: O(n) Space: O(h)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY
- Count Good Nodes in Binary TreeMEDIUM