88. Binary Tree Maximum Path Sum
Choose a path that follows parent-child edges and includes each chosen node at most once. The path may begin and end anywhere in the tree, and you want the largest sum of its node values.
A path cannot split into multiple branches. Since the path must be nonempty, an all-negative tree still requires choosing at least one node.
Example 1
Input
[-10,9,20,null,null,15,7]
Output
OptionalLong[42]
Explanation: The path 15–20–7 beats every path through root -10.
Example 2
Input
[-3,-2,-5]
Output
OptionalLong[-2]
Explanation: A nonempty optimum may be a single negative node; zero is not allowed as the answer.
Example 3
Input
[MAX,MAX,MAX]
Output
OptionalLong[6442450941]
Explanation: The three-node sum exceeds int capacity.
Constraints
0 <= node count per tree <= 105-231 <= node.value <= 231 - 1- Each input is a proper binary tree: no cycles or shared child nodes. Null trees are permitted.
Hints
Hint 1
What may a child return that can still be extended by its parent?
Hint 2
Negative child arms are optional, but the current node is not.
Hint 3
In postorder, update best with value+both nonnegative arms and return value+the better one.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
The winning path can avoid the root
[-10,9,20,null,null,15,7]
{"present":true,"value":42}