906. Maximum subtree sum
You are given a binary tree and an array nums. Each node of the binary tree contains an integer x, which represents its index in the array nums. The value associated with the node is nums[x].
You need to find the node whose subtree has the maximum sum of associated values and return the node and the maximum subtree sum.
Example 1:
Input : nums = [1, 2, 3, 4, 5, 6], root = 1 2 3 null 4 5 6
Output : 1 21
Explanation :
The 6th node subtree sum is -> 6.
The 5th node subtree sum is -> 5.
The 4th node subtree sum is -> 4.
The 3rd node subtree sum is -> 3 + 5 + 6 -> 14.
The 2nd node subtree sum is -> 2 + 4 -> 6.
The 1st node subtree sum is -> 1 + 2 + 3 + 4 + 5 + 6 -> 21.
Example 2:
Input : nums = [1, -4, 3, -2, 5, 6], root = 1 2 3 null 4 5 6
Output : 3 14
Explanation :
The 6th node subtree sum is -> 6.
The 5th node subtree sum is -> 5.
The 4th node subtree sum is -> -2.
The 3rd node subtree sum is -> 3 + 5 + 6 -> 14.
The 2nd node subtree sum is -> (-4) + (-2) -> -6.
The 1st node subtree sum is -> 1 + (-4) + 3 + (-2) + 5 + 6 -> 9.
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- -105<= nums[i] <=105