LeetCode 124 · Hard · Trees

Binary Tree Maximum Path Sum

A path runs between any two nodes along parent-child links, using each node at most once; it need not pass through the root. Return the largest sum of values over all non-empty paths.

O(n)time
O(h)space · call stack
DFSreturn one arm, score the bend

level order as on LeetCode, null = no child · 1 to 15 nodes, 4 levels · values −99 to 99

Call stack one frame per dfs call · newest on the right · badges = returned gain of the best downward arm

private int res;public int maxPathSum(TreeNode root) { res = root.val; dfs(root); return res;}private int dfs(TreeNode root) { if (root == null) { return 0; } int leftMax = Math.max(dfs(root.left), 0); int rightMax = Math.max(dfs(root.right), 0); res = Math.max(res, root.val + leftMax + rightMax); return root.val + Math.max(leftMax, rightMax);}
root
—
leftMax
—
rightMax
—
res
—
return
—

Why it works

  1. Brute force sums the path between every pair of nodes: O(n²) pairs, each path up to O(h) long.
  2. Every path bends at exactly one highest node. There it is node.val plus the best arm down the left plus the best arm down the right. So each node scores its own bend into res, and the answer is the best bend anywhere.
  3. A parent can only extend one arm, so a call returns val + Math.max(leftMax, rightMax), not the bend. Each node is visited once: O(n) time, O(h) stack.
  4. Pitfall: negative arms. An arm that sums below zero only hurts, so Math.max(…, 0) drops it. And res must start at root.val, not 0: in an all-negative tree the answer is the single largest value, which is below zero.
  5. Same shape: Diameter of Binary Tree (543) counts edges instead of summing values; the return-one-arm, score-the-bend split is identical.