House Robber III

Medium

Houses are arranged as a binary tree. You cannot rob two directly-connected houses (a parent and its child) on the same night. Given the root, return the maximum amount of money you can rob without alerting the police.

Example 1

Input:  root = [3,2,3,null,3,null,1]
Output: 7

Example 2

Input:  root = [3,4,5,1,3,null,1]
Output: 9

Constraints

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