House Robber III

The houses in this neighborhood form a binary tree: the root is one house, and each node's children are the houses directly connected to it. The alarm rings only if two directly-linked houses (a parent and one of its children) are robbed on the same night.

Given the root of the tree, return the maximum amount of money you can rob without alerting the police.

Input / output

• Input: root: TreeNode (the JSON test fixture is a LeetCode-style level-order array using null for missing children, for example [3,2,3,null,3,null,1])
• Output: int (maximum loot)

Examples

1. root = [3,2,3,null,3,null,1] returns 7 by robbing the root and both grandchildren (3 + 3 + 1).
2. root = [3,4,5,1,3,null,1] returns 9 by robbing the two children (4 + 5).
3. root = [4] returns 4.

Constraints

• 0 <= number of nodes <= 10^4
• 0 <= Node.val <= 10^4

Follow-up A naive recursion recomputes grandchildren repeatedly. Can you make each node return both "best if I rob this node" and "best if I skip it" so the whole tree is solved in a single O(n) postorder pass?