House Robber III
Houses in a neighborhood are arranged in a binary tree structure. Each house holds a certain amount of money, and directly connected houses (parent and child) have linked security systems. The robber cannot rob two directly linked houses on the same night. Return the maximum amount of money that can be robbed.
root = [3, 2, 3, null, 3, null, 1]
7
The root holds 3, its children hold 2 and 3, and the two grandchildren hold 3 and 1. Robbing the root (3) forces skipping both children, leaving the grandchildren: 3 + 3 + 1 = 7. Robbing the children instead gives only 2 + 3 = 5.
root = [3, 4, 5, 1, 3, null, 1]
9
Skipping the root lets both children be robbed: 4 + 5 = 9. Robbing the root would give 3 plus the grandchildren 1 + 3 + 1 = 8, which is worse. The best choice at a node depends on the whole subtree, not on the node's own value.
The number of nodes in the tree is in the range [1, 10^4]0 <= Node.val <= 10^4