Binary Tree Maximum Path Sum
You're given the root of a binary tree whose node values may be negative. A path is a sequence of nodes where each adjacent pair is joined by an edge and no node appears more than once. A path must contain at least one node, but it does not have to pass through the root or end at a leaf. Return the largest possible sum of the node values on any path.
Examples
root = [1,2,3] returns 6
The path 2 -> 1 -> 3 uses every node and sums to 2 + 1 + 3 = 6.
root = [-10,9,20,null,null,15,7] returns 42
The path 15 -> 20 -> 7 sums to 42. Stretching it up through -10 to 9 would give 34, so the best path leaves the root out.
root = [-3,-1,-2] returns -1
Every value is negative, so adding a second node only lowers the sum. The best path is the single node -1, and the answer is negative.
Constraints
- 1 <= number of nodes <= 3 * 10^4
- -1000 <= Node.val <= 1000
Hints
Every path has one topmost node where it may bend. What is the best path that bends at a given node, and what can that node offer its parent?
Use post-order depth-first search: each call returns the best sum of a path going straight down from that node, while a separate variable tracks the best bent path seen anywhere.
gain(node): return 0 for null. left = max(gain(node.left), 0), right = max(gain(node.right), 0). Update best with node.val + left + right, then return node.val + max(left, right). Start best at negative infinity.
Drill This: Your Approach First
Approach
Post-order depth-first search (DFS) where each call returns the node's best downward gain: node.val plus the larger child gain, with a negative child gain clamped to 0 (leave that side out). The best path that bends at a node is node.val + leftGain + rightGain, so track the global max of that. Only one side can be passed up to the parent, because a path cannot fork. O(n) time, O(h) space for recursion, h = tree height.
Time
O(n)
Space
O(h)
Pitfall
Solutions
class Solution {
private int best;
public int maxPathSum(TreeNode root) {
best = Integer.MIN_VALUE;
gain(root);
return best;
}
private int gain(TreeNode node) {
if (node == null) return 0;
int left = Math.max(gain(node.left), 0);
int right = Math.max(gain(node.right), 0);
best = Math.max(best, node.val + left + right);
return node.val + Math.max(left, right);
}
}from typing import Optional
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
best = float("-inf")
def gain(node: Optional[TreeNode]) -> int:
nonlocal best
if not node:
return 0
left = max(gain(node.left), 0)
right = max(gain(node.right), 0)
best = max(best, node.val + left + right)
return node.val + max(left, right)
gain(root)
return best