House Robber III
Problem statement
The houses in a neighborhood are connected like a binary tree. Each node is a house, and its value is the amount of money in that house. root is the first house.
You may take money from any houses you like, but you can never take from two houses that are directly connected: a house and its parent, or a house and its child. Two houses with the same parent are not directly connected, so you may take both.
Return the largest total amount of money you can take.
Function
rob(root: TreeNode) → intExamples
Example 1
root = [4,2,6,null,5,null,1]return = 11House 4 is the root. Its children are 2 and 6. House 2 has child 5, and house 6 has child 1.
Take houses 5 and 6 for 5 + 6 = 11. They are on different levels, but they are not directly connected. Taking the root with 5 and 1 gives only 4 + 5 + 1 = 10.
Example 2
root = [1,10,1,null,null,10,10]return = 30The root 1 has children 10 and 1, and the right child 1 has two children of 10.
Skip the root and its right child. Take the left child and the two bottom houses for 10 + 10 + 10 = 30.
Example 3
root = [2,1,null,1,null,2]return = 4The houses form one line going down: 2, then 1, then 1, then 2.
Take the top and the bottom house for 2 + 2 = 4. Skipping two houses in a row in the middle is allowed.
Constraints
- The number of nodes in the tree is between
1and10^4. 0 <= Node.val <= 10^4- The depth of the tree is at most
500. The root alone has depth1.