Problem overview
A path in a binary tree is a sequence of nodes where each is joined to the next by an edge, with no node repeated. It has at least one node and needn't pass through the root. Its sum is the total of its node values. The method maxPathSum gets the root of a tree and returns the largest path sum. The lesson provides the TreeNode class, with an Int field value and the fields left and right, which are null for a missing child.
For the tree [1, 2, 3] the best path is 2 -> 1 -> 3, with sum 6. For [-10, 9, 20, null, null, 15, 7] it is 15 -> 20 -> 7, with sum 42: going up to the root would add -10. For [-2, -1, -3] every value is negative, so the best path is the single node -1.
Approach: every node gets a turn as the top of the path
A path goes up from one node to a highest node and then down to another. Two things follow from that:
- Every path has exactly one highest node, where it bends (or where it starts or ends, if it only goes one way). So the answer is the best sum over all nodes of "the best path whose highest node is this one".
- For a node, that best path is the node's value, plus the best downward path into the left child, plus the best downward path into the right child. A downward path starts at a node and keeps going through one child at a time, or stops.
A subtree whose best downward path is negative only lowers the total, so it is replaced by 0, which means leaving that side out. That is also why the answer can't start at 0: if every value is negative, the best path is a single node, and 0 would beat it.
The recursion helper returns something slightly different from what the answer needs. A parent can extend a path from a child only one way, because a path through both children of the child can't also go up to the parent. So maxGain(node) returns the best path that starts at node and goes down one side, while the bent path through node is only recorded in a field, best.
For [-10, 9, 20, null, null, 15, 7], maxGain of node 20 is 35: the value 20 plus the better child, 15. At node 20 the bent path 15 -> 20 -> 7 gives 42, which becomes best. At the root the path through both sides would be -10 + 9 + 35 = 34, which doesn't beat 42.
Each node is visited once, so the time is O(n), where n is the number of nodes.
Step by step
maxPathSum
- Keep the best sum in a field. A
var bestin the class lets the helper update it whilemaxPathSumreads it at the end. It starts at 0 only as a placeholder. - Set
besttoroot.valueat the start of the method. The root alone is a path, so the answer is at least that. This is safe for all-negative trees. - Call
maxGain(root)and ignore its result. The walk updatesbestas it goes, and one call from the root reaches every node. - Return
best.
maxGain
- Declare the helper as
def maxGain(node: TreeNode): Int. It returns the largest sum of a path that starts atnodeand goes down one side, or stops atnode. - Empty subtree: if
nodeisnull, return 0. This ends the recursion and adds nothing to a path. - Left gain:
math.max(0, maxGain(node.left)), stored inleft. A negative side is dropped. - Right gain: the same for
node.right, stored inright. Both children finish before the node itself uses their answers. - Try this node as the bend:
node.value + left + rightis the best path with this node on top. Setbestto the larger of its old value and that sum. - Return the one-way gain:
node.value + math.max(left, right). The parent can extend only one side.
The solution in Scala
class Solution {
var best = 0
def maxGain(node: TreeNode): Int = {
if (node == null) {
return 0
}
val left = math.max(0, maxGain(node.left))
val right = math.max(0, maxGain(node.right))
best = math.max(best, node.value + left + right)
return node.value + math.max(left, right)
}
def maxPathSum(root: TreeNode): Int = {
best = root.value
maxGain(root)
return best
}
}
The Scala details worth noticing:
- A
varin the class body is a field. Every method of the instance sees and updates the samebest. Setting it at the start ofmaxPathSummeans a second call on the same object doesn't inherit the result of the first. math.maxtakes two numbers and returns the larger one.mathis thescala.mathpackage object, available without an import.node == nullis a plain comparison. Fornullchecks on a class likeTreeNode,==is the usual form.- Calling a method for its side effect. The statement
maxGain(root)throws the returnedIntaway. That is deliberate: the answer is inbest. - Recursion depth. The tree is at most 400 levels deep, so the recursion stays shallow. A chain of 400 nodes of value 1 returns 400.
Complexity
Time: O(n). maxGain is called once for each node and once for each missing child, and every call does a constant amount of work.
Space: O(h) for the call stack, where h is the height of the tree. It is at most 400 here, and about log n for a balanced tree.
Edge cases and common mistakes
- All values negative.
[-2, -1, -3]returns -1. Startingbestat 0 would return 0, which is not the sum of any path. - One node.
[5]returns 5, and[-7]returns -7. - A negative child next to a positive node.
[2, -1]returns 2: the child's gain is clamped to 0, so the path stays on the node alone. - The best path avoids the root. In
[-10, 9, 20, null, null, 15, 7], the answer 42 sits entirely under the root. Only the bent sum at each node records it. - Returning the bent sum to the parent. If
maxGainreturnednode.value + left + right, a parent could extend a path that already goes down both sides of the child, which is not a path. For the tree[1, 2, null, 3, 4], where 2 is the left child of 1 and has the children 3 and 4, that mistake gives 10 instead of the correct 9. Return only one side. - Forgetting to clamp. Using
maxGain(node.left)withoutmath.max(0, ...)adds negative branches. For[1, -2, 3]this gives 3 instead of 4. - Using the larger side only for the bent sum. The bend needs both sides.
[1, 2, 3]would then return 4 instead of 6.
Testing
[1, 2, 3]gives 6.[-10, 9, 20, null, null, 15, 7]gives 42.[-2, -1, -3]gives -1.[5]gives 5.[-7]gives -7.[2, -1]gives 2.[1, -2, 3]gives 4.
