You sell sweets door to door before Diwali in a village. The houses are placed like the nodes of a binary tree. You enter the village at the house root. Every other house has exactly one parent house above it. The value of a house is how many rupees of sweets it will buy.
Neighbours talk: if you sell to two houses that are directly linked (a parent and its child), the second customer cancels the order. So you may not choose both houses of such a pair.
Given the root of the tree, return the largest total amount you can earn.
A binary tree arrives as an array in level order, with null for a missing child (for example [3,9,20,null,null,15,7]; [] is an empty tree). The array is the way the judge sends the tree to your function. You do not build or use TreeNode objects.
How the judge passes the data
Examples
Example 1:
Input: root = [2,1,3,null,4]
Output: 7
Explanation: Sell to the house with 3 and the house with 4. They are not directly linked, so the total is 7.
Example 2:
Input: root = [6,1,2]
Output: 6
Explanation: Selling to the root alone gives 6, which is more than 1 + 2 = 3.
Example 3:
Input: root = [4,10,2,null,null,6,8]
Output: 24
Explanation: Sell to the houses with 10, 6 and 8. None of them is directly linked to another. The total is 24.