The houses are organized as a binary tree. If two directly-linked houses are robbed on the same night, the police are alerted. Return the maximum money you can rob. Node definition: { val: number, left: TreeNode | null, right: TreeNode | null }.
Examples
Input:root = [3,2,3,null,3,null,1]
Output:7
Rob root (3) and leaf (1), and leaf (3). Total = 3 + 1 + 3 = 7.
Constraints
• The number of nodes in the tree is in the range [1, 10^4].
• 0 <= Node.val <= 10^4
Complexity Analysis
Time
O(n)
single post-order DFS traversal of nodes.
Space
O(h)
where h is the height of the tree, representing stack depth.