Loading problem…
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called `root`. Besides the `root`, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a **binary tree**. It will automatically contact the police if **two directly-linked houses were broken into on the same night**. Given the `root` of the binary tree, return the **maximum amount of money** the thief can rob **without alerting the police**.
Example 1
Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Rob the root (3) and the two grandchildren (3 and 1): 3 + 3 + 1 = 7, and no two robbed houses are directly linked.
Example 2
Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Rob the two children 4 and 5 (total 9); robbing the root would forbid both and yield less.
Example 3
Input: root = [4]
Output: 4
Explanation: There is only one house, so the thief robs it for 4.
For each node compute two numbers in one post-order pass: the best loot if we ROB this node (then its children must be skipped) and the best if we SKIP it (children are free to choose their own best). A parent combines its children's pairs; the answer is the max of the root's pair.
Run checks all cases above. Submit evaluates all test cases.