Binary Trees Depth first: return a value up
353. Binary Tree Maximum Path Sum
You are given root, the root node of a binary tree. Return the largest sum of the values on a path in the
tree.
A path goes from one node to another along the links of the tree, each step from a node to its parent or to one of its children, and it never visits a node twice. A single node is a path too, but a path cannot be empty. The path does not have to pass through the root. Its sum is the sum of the values of all the nodes on it.
The examples write a tree level by level, from left to right, with null where a child is missing. So
root = [5,8,null,3] is the root 5 with a left child 8 and no right child, and 8 has a left child 3. The
missing children after the last node are left out.
Example 1
Input: root = [2, -6, 5, 4, 8, null, -1, null, null, 3]
12Explanation: The best path is 3 → 8 → −6 → 2 → 5, with the sum 3 + 8 − 6 + 2 + 5 = 12. It passes through −6, because the nodes it reaches beyond −6 add more than 6. The path 3 → 8 alone has the sum 11.
Example 2
Input: root = [-4, -2, -7]
-2Explanation: Every value is negative, so every node added to a path makes its sum smaller. The best path is the single node −2.
Example 3
Input: root = [1000000000, 1000000000, 1000000000, 1000000000]
4000000000Explanation: The best path uses all four nodes: from the bottom-left node up to the root, then down to its right child.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ number of nodes ≤ 105-109 ≤ Node.val ≤ 109- The tree has at most 1000 levels.
Clarifying questions
What you would ask an interviewer before writing any code.