House Robber III
You are given a binary tree where each node stores money in one house. The tree is provided as a level-order array, and null means that child is missing.
You cannot rob two houses that are directly connected by an edge (parent and child). If you rob one house, you must skip its immediate children.
Return the maximum total amount you can rob from the tree without breaking that rule.
Examples
Input: [3,2,3,null,3,null,1]
Output: 7
Input: [3,4,5,1,3,null,1]
Output: 9
Hints
Start by considering the problem recursively: for any given node, you have two choices - either rob it (and skip its children) or skip it (and consider robbing its children).
For each node, calculate two values: the maximum amount you can rob if you rob this node (`rob`), and the maximum amount if you skip this node (`skip`). These values should be computed based on the same values from its children.
Use dynamic programming to store the results of subproblems (i.e., the `rob` and `skip` values for each node) to avoid redundant calculations, and ensure that the solution runs in O(n) time where n is the number of nodes in the tree.
Related Problems
House Robber III
You are given a binary tree where each node stores money in one house. The tree is provided as a level-order array, and `null` means that child is missing.