Description
The thief has found himself a new place for his thievery again. The houses form a binary tree. It will automatically contact the police if two directly-linked houses were broken into. Return the maximum money the thief can rob.
Examples
Input:
root = [3,2,3,null,3,null,1]Output:
7Explanation:
Rob nodes 3 + 3 + 1 = 7.
Input:
root = [4,1,2,null,3,null,5]Output:
9Explanation:
Rob houses with values 4 and 5 (4 + 5 = 9). Cannot rob adjacent houses 1 and 2.
Input:
root = [5,4,8,1,null,6,3]Output:
17Explanation:
In the tree [5,4,8,1,null,6,3], the optimal robbery selects a non-adjacent set of nodes summing to 17.
Constraints
- •
1 ≤ number of nodes ≤ 10⁴ - •
0 ≤ Node.val ≤ 10⁴