Given the root of a binary tree of integers, return the maximum path sum.
HardA path in a binary tree is a sequence of nodes where each pair of neighbors is joined by an edge and no node appears more than once. A path doesn't have to pass through the root. Its path sum is the total of the values on it.
Given the root of a binary tree, return the largest path sum of any non-empty path.
Trees in the examples and tests are written in level order, with null for a missing child.
Example 1
Input: root = [1, 2, 3] Output: 6
The best path is 2 -> 1 -> 3.
Example 2
Input: root = [-10, 9, 20, null, null, 15, 7] Output: 42 -10 / \ 9 20 / \ 15 7
The best path is 15 -> 20 -> 7, which skips the root.
Constraints
- The tree has between
1and3 * 10^4nodes. -1000 <= Node.val <= 1000
Approach
Every path has a single highest node, where it turns from going up to going down. With that node fixed, the best path through it is its value plus the best downward path into its left subtree and the best downward path into its right subtree, dropping either side if it would only lower the total.
A post-order traversal computes both things at once. For each node, it first gets the best downward sums from its children, treating negative ones as 0. It updates the overall answer with the path that turns at this node. Then it returns the node's value plus the better of its two children, because a parent can only extend a path that goes straight down.
Steps
- Set
bestto negative infinity. - Define
gain(node): return0for an empty node. Otherwise, computeleft = max(gain(node.left), 0)andright = max(gain(node.right), 0). - Update
bestwithnode.val + left + right, then returnnode.val + max(left, right). - Call
gain(root)and returnbest.
Complexity
- Time:
O(n). Each node is visited once. - Space:
O(h)for the recursion stack, wherehis the height of the tree.
Common mistakes
- Returning the turning path,
node.val + left + right, to the parent. A parent can only extend a path that goes straight down through one child. - Starting
bestat0. If every value is negative, the answer is the largest single value, which is below0.






