220. House Robber III

MediumTree

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**.

Examples

Input: [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.

Constraints

The number of nodes in the tree is in the range [1, 10^4].
0 <= Node.val <= 10^4

Run checks all cases above. Submit evaluates all test cases.