House Robber III

Given the root of a binary tree where each node contains a non-negative amount of money, return the maximum amount you can rob without robbing two directly connected nodes. This is a classic tree DP problem because each node needs two states: robbed or not robbed.

Input Format

tree = level-order binary tree with null markers

Output Format

maximum amount that can be robbed

Constraints

• 1 <= number of nodes <= 10^5
• Node values are non-negative integers.
• The tree is given in level-order form with null markers.

Examples

tree = [3,2,3,null,3,null,1]

7

tree = [3,4,5,1,3,null,1]

9