Problem overview
The method maxPathSum(_ root: TreeNode?) -> Int returns the largest path sum in a binary tree. A path is a sequence of nodes joined by edges, with no node repeated. It has at least one node, and it needn't pass through the root. The path sum is the sum of the node values. The lesson provides the TreeNode class, with val, left and right.
For the tree [1, 2, 3] the best path is 2, 1, 3, with sum 6. For [-10, 9, 20, nil, nil, 15, 7] it is 15, 20, 7 with sum 42: continuing 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 path has one highest node
A path goes up from one node to a highest node and then down to another, or stays on one side. Either way it bends at most once, at its highest node. So the answer is the best value, over all nodes, of "this node as the highest point of the path".
For a node, that value is node.val plus the best downward path into the left child plus the best downward path into the right child. A downward path that would have a negative sum is better left out, so each side counts as at least 0.
To get those side values, a helper maxGain returns, for a node, the largest sum of a path that starts at that node and goes down through one child at a time, or stops at the node. The parent can extend only one side of a path: a path that already uses both children of a node can't also continue up to the parent. So maxGain returns node.val plus the larger side, not both.
The helper does two jobs. It updates a running best using both sides, and it returns one side to its caller. The tree is visited once, so the work is O(n).
Step by step
- Keep the best sum in a property:
var best = 0in the class, which every method of the class can read and write. - Start it at the root's value:
best = root!.val. The root alone is a path, and the tree has at least one node. Zero would be a wrong start, since every value may be negative. - Call the helper on
rootand assign its result to_. The helper's result isn't needed here, and_ =says so to the compiler, which otherwise warns about an unused result. - Return
best. - Declare
maxGain(_ node: TreeNode?) -> Intfor the best downward path from a node. - Stop on an empty subtree:
guard let node = node else { return 0 }. An empty subtree adds nothing. After the guard,nodeis a plainTreeNode. - Get the left gain, at least 0:
max(0, maxGain(node.left))in aletnamedleft. - Get the right gain the same way, in
right. Both children are processed before this node, because this node needs their answers. - Try this node as the highest node:
best = max(best, node.val + left + right). - Return the one-way gain:
node.val + max(left, right).
The solution in Swift
class Solution {
var best = 0
func maxGain(_ node: TreeNode?) -> Int {
guard let node = node else {
return 0
}
let left = max(0, maxGain(node.left))
let right = max(0, maxGain(node.right))
best = max(best, node.val + left + right)
return node.val + max(left, right)
}
func maxPathSum(_ root: TreeNode?) -> Int {
best = root!.val
_ = maxGain(root)
return best
}
}
The Swift details worth a closer look:
- The property.
bestlives in theSolutionobject, somaxGaincan update it as it recurses without passing it around.maxPathSumsets it at the start of every call, so reusing the sameSolutionobject for a second tree works:[1, 2, 3]gives 6, and then[-5]gives -5. guard let node = nodeshadows the optional parameter with a non-optional constant of the same name for the rest of the function. Theelseblock must leave the function, here by returning 0._ = maxGain(root). Without the_ =, Swift warns that the result is unused. The call is there for its effect onbest.max. Swift's globalmax(_:_:)compares two values of the same type.max(0, maxGain(node.left))is the clamp that drops negative sides.- Methods can call each other in any order. The helper is written above
maxPathSumin the lesson, but inside a class the order of methods doesn't matter to the compiler.
Complexity
Time: O(n). maxGain runs once per node, with constant work in each call, plus one call on a missing child for each missing side.
Space: O(h), where h is the height of the tree: one call per level on the path from the root down. That is at most 400 here, well within the call stack. A skewed tree is the worst case.
Edge cases and common mistakes
- All negative values. Starting
bestat 0 would return 0 for[-2, -1, -3], where the right answer is -1. - Not clamping the sides. Without
max(0, ...), the tree[1, -2, 3]would give 3, the lone node 3, instead of 4: the root adds its left side, -2, to the sum, so the path 1, 3 is never considered. With the clamp, the answer is 4. - Returning both sides to the parent. A path can't fork. Returning
node.val + left + rightwould count paths that go down two ways. - Single node.
[5]gives 5, and[-3]gives -3. - Two children, one useful.
[2, -1]gives 2: the left child would only lower the sum.
Testing
[1, 2, 3]gives6.[-10, 9, 20, nil, nil, 15, 7]gives42.[-2, -1, -3]gives-1.[5]gives5.[-3]gives-3.[2, -1]gives2.[1, -2, 3]gives4.[-1, 5, nil, 4]gives9.[9, 6, -3, nil, nil, -6, 2, nil, nil, 2, nil, -6, -6, -6]gives16.
