Binary Tree Maximum Path Sum Hard 0 attempts
LeetCode ↗

Binary Tree Maximum Path Sum

Hard TreeBinary TreeDFS LeetCode

You're given the root of a binary tree. A path is any sequence of nodes connected edge to edge, visiting each node at most once, and it isn't required to start or end at the root or pass through it. Find the path whose node values sum to the largest total, and return that sum.

Input Format
Implement maxPathSum(root). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
root = [-10,9,20,null,null,15,7]
Output
42

Example 2

Input
root = [-3]
Output
-3
Constraints
  • 1 <= number of nodes <= 3 * 10^4
  • -1000 <= Node.val <= 1000
Test Cases (2)
Case 1
Args: [[-10,9,20,null,null,15,7]] Expected: 42
Case 2
Args: [[-3]] Expected: -3
Topics
TreeBinary TreeDFS

Iterative Postorder

For each node, retain the best downward path. Its best full path combines the node with positive gains from both children; the downward value passed to its parent uses only one child.

javascript
function maxPathSum(root) {
  if (!root) return 0;
  const order = [], stack = [root];
  while(stack.length) {
    const node=stack.pop();order.push(node);
    if(node.left)stack.push(node.left);
    if(node.right)stack.push(node.right);
  }
  const gains=new Map();let best=-Infinity;
  for(let i=order.length-1;i>=0;i--) {
    const node=order[i],l=Math.max(0,gains.get(node.left)||0),r=Math.max(0,gains.get(node.right)||0);
    best=Math.max(best,node.val+l+r);gains.set(node,node.val+Math.max(l,r));
  }
  return best;
}

Time: O(n) | Space: O(n) auxiliary space, excluding output

Saved in this browser only. Private to you.

JavaScript