Binary Tree Maximum Path Sum
Post-order DFS returns the best single-arm gain; meanwhile track the best path bending at any node.
Problem#
Given the root of a binary tree, return the maximum sum of any path. A path can start and end at any nodes and goes through parent-child connections.
Examples#
[1,2,3]→6(2 + 1 + 3)[-10,9,20,null,null,15,7]→42(15 + 20 + 7)
Constraints#
- The number of nodes is in
[1, 3 * 10^4].-1000 <= Node.val <= 1000.
Approach#
Each path can be decomposed into a “left arm + node + right arm” at its highest node. DFS each node returns the best single-arm gain (max of zero, left arm, right arm — clamping negatives to 0 means skip that branch). Track globally the best bend left + node + right at every node.
Solution#
class Solution {public: int maxPathSum(TreeNode* root) { int best = INT_MIN; function<int(TreeNode*)> dfs = [&](TreeNode* u) -> int { if (!u) return 0; int l = max(0, dfs(u->left)); int r = max(0, dfs(u->right)); best = max(best, u->val + l + r); return u->val + max(l, r); }; dfs(root); return best; }};func maxPathSum(root *TreeNode) int { best := math.MinInt32 var dfs func(u *TreeNode) int dfs = func(u *TreeNode) int { if u == nil { return 0 } l := max(0, dfs(u.Left)) r := max(0, dfs(u.Right)) if u.Val+l+r > best { best = u.Val + l + r } return u.Val + max(l, r) } dfs(root) return best}from typing import Optional
class Solution: def maxPathSum(self, root: Optional[TreeNode]) -> int: best = float('-inf')
def dfs(u: Optional[TreeNode]) -> int: nonlocal best if not u: return 0 l = max(0, dfs(u.left)) r = max(0, dfs(u.right)) best = max(best, u.val + l + r) return u.val + max(l, r)
dfs(root) return bestvar maxPathSum = function(root) { let best = -Infinity; const dfs = (u) => { if (!u) return 0; const l = Math.max(0, dfs(u.left)); const r = Math.max(0, dfs(u.right)); best = Math.max(best, u.val + l + r); return u.val + Math.max(l, r); }; dfs(root); return best;};class Solution { private int best;
private int dfs(TreeNode u) { if (u == null) return 0; int l = Math.max(0, dfs(u.left)); int r = Math.max(0, dfs(u.right)); best = Math.max(best, u.val + l + r); return u.val + Math.max(l, r); }
public int maxPathSum(TreeNode root) { best = Integer.MIN_VALUE; dfs(root); return best; }}function maxPathSum(root: TreeNode | null): number { let best = -Infinity; const dfs = (u: TreeNode | null): number => { if (!u) return 0; const l = Math.max(0, dfs(u.left)); const r = Math.max(0, dfs(u.right)); best = Math.max(best, u.val + l + r); return u.val + Math.max(l, r); }; dfs(root); return best;}Editorial#
The key insight: a single recursive call returns the best path that continues upward through the parent, which forbids using both arms. But at the bend node itself, we can use both. Track the bend value separately while returning only the straight-up extension.
Complexity#
- Time: O(n).
- Space: O(h).
Concept revision#
Related#