Problem overview
The method maxPathSum(root) receives the root of a binary tree with at least one node and returns the largest path sum in it. A path is a sequence of nodes where each is joined by an edge to the next, no node appears twice, and the path has at least one node. It need not pass through the root. The path sum is the sum of the node values on it, and values can be negative. The lesson provides the TreeNode type: a node has a number val and two children, left and right, each a node or null.
For the tree [1,2,3] the best path is 2, 1, 3 with the sum 6. For [-10,9,20,null,null,15,7] it is 15, 20, 7 with the sum 42: going on to the root would add -10 and lower it. For [-2,-1,-3] every value is negative, so the best path is the single node -1.
Approach: every node tries to be the top of a path
Any path has a highest node, the one closest to the root. The path goes down from it on the left side, on the right side, or on both, and it can bend only there. So the answer is the best value of "this node plus its best downward path on the left plus its best downward path on the right", taken over all nodes.
That suggests a helper, maxGain(node), which returns the largest sum of a path that starts at node and goes down through one child at a time, or stops at node. Two things follow:
- A negative branch is better left out. If a child's best downward path is below 0, the node is better off without it, so each side counts as
Math.max(0, ...). - The parent can use only one side. A path that goes down both sides of a node can't also continue up to that node's parent, because the node would then sit between three neighbours. So
maxGainreturns the node's value plus only the larger side.
Each node is visited once, as the "top" candidate and as a piece the parent may extend. That gives linear time.
Here is the helper on [-10,9,20,null,null,15,7]. The nodes are finished in this order, each returning its gain: node 9 returns 9, node 15 returns 15, node 7 returns 7, node 20 returns 35, and node -10 returns 25. The best sum seen so far is 9, then 15, then 42 at node 20 (20 + 15 + 7), and it stays 42 at the root.
Step by step
- Keep the best sum in the class. A property
best, a number, starts at 0. Every method can see it, so the helper updates it whilemaxPathSumreads it at the end. - Start it at the root's value. In
maxPathSum,this.best = root.val. The root alone is a path, and every value may be negative, so 0 would be a wrong start: the answer for[-3]is -3. - Walk the tree with
this.maxGain(root). Its return value isn't needed here, because it updatesthis.beston the way. - Return
this.best. - Write the helper
maxGain(node: TreeNode | null): number. - Base case. A
nullnode returns 0: an empty subtree adds nothing. - Left gain.
leftis the larger of 0 andthis.maxGain(node.left). - Right gain.
rightis computed the same way. Both children are handled before the node itself, since the node needs their answers. - Try this node as the top. The path that comes up from the left and goes down the right has the sum
node.val + left + right. Updatethis.bestwithMath.max. - Return the one-sided gain:
node.val + Math.max(left, right).
The solution in TypeScript
class Solution {
best: number = 0;
maxGain(node: TreeNode | null): number {
if (node === null) {
return 0;
}
let left = Math.max(0, this.maxGain(node.left));
let right = Math.max(0, this.maxGain(node.right));
this.best = Math.max(this.best, node.val + left + right);
return node.val + Math.max(left, right);
}
maxPathSum(root: TreeNode | null): number {
this.best = root.val;
this.maxGain(root);
return this.best;
}
}
Details worth knowing:
- A class property.
best: number = 0;declares a field with a type and a starting value. EachSolutionobject has its ownbest, and methods reach it asthis.best. The method sets it again at the start ofmaxPathSum, so the 0 is only a placeholder. - Two different "bests".
this.bestis the answer so far, which may bend at a node. The return value ofmaxGainis something else: a path the parent can extend, so it never has two branches. Math.max(0, ...)and negative numbers. The clamp applies to the children's gains, not tonode.val. A node's own value always counts, because a path must contain at least one node.numberis a double. The sums stay far below 2^53 here (at most 30,000 nodes with values up to 1000 in size), so they are exact.- Types are erased.
TreeNode | nullis a note for the compiler. The lesson's settings don't make it reportroot.valas possiblynull, and the constraints promise at least one node.
Complexity
Time: O(n), where n is the number of nodes. maxGain runs once per node, plus one call per missing child, and each call does a constant amount of work.
Space: O(h) for the recursion, where h is the height of the tree: at most the 400 levels the constraints allow, or O(log n) for a balanced tree.
Edge cases and common mistakes
- All values negative.
[-2,-1,-3]gives -1. Startingbestat 0 would wrongly return 0, which is not the sum of any path. That is why it starts atroot.val. - A single node.
[5]gives 5 and[-3]gives -3. - A path that skips the root. In
[-10,9,20,null,null,15,7]the answer 42 doesn't include the root. - Returning both sides. Returning
node.val + left + rightfrommaxGainwould let a parent extend a path that already bends, producing a sum no path has. Only the update ofthis.bestuses both sides. - Forgetting to clamp. Without
Math.max(0, ...), a negative child is always added. For[1,-2,3]the answer is 4 (the path 1, 3, not through -2). - Skipping a node's own value. The sum must include
node.val, even if it is negative, since a path has at least one node.
Testing
[1,2,3]gives6.[-10,9,20,null,null,15,7]gives42.[-2,-1,-3]gives-1.[5]gives5.[-3]gives-3.[2,-1]gives2.[1,-2,3]gives4.[-1,5,null,4,null,-3]gives9.
