Problem overview
The method maxPathSum(root) receives the root of a binary tree and returns the largest sum of any path 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 doesn't have to pass through the root. The lesson provides the TreeNode class, with val, left and right, as shown in a comment in the starter code.
For the tree [1, 2, 3] the best path is 2, 1, 3 with the sum 6. For [-10, 9, 20, None, None, 15, 7] the best path is 15, 20, 7 with the sum 42: continuing 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 highest point
Any path in a tree has a highest node, the one closest to the root, and the path bends there at most once: it comes up one side and goes down the other (or only one side, or neither). So the answer is the best, over all nodes, of the sum of that node's value plus the best downward path into its left subtree plus the best downward path into its right subtree.
That needs one 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. It is the value a parent can use if it wants to extend a path into this node. It can only be one side, because a path that already went down both sides of a node can't also continue up to that node's parent: it would need to visit the node twice.
A negative gain should never be used. If the best way down through a child has a negative sum, the path is better off not entering that child at all, which counts as a gain of 0. That is why each child's result is wrapped in max(0, ...). This is only for the children: the node itself must always be on the path, since a path has at least one node. The running best therefore starts at root.val and not at 0, because with all values negative, 0 would be an answer no path can reach.
One walk from the root visits every node once, so the time is O(n).
Step by step
- Start the best sum at the root's value. Store
root.valinself.best. The root alone is a path, so the answer is at least that. An attribute onselfis visible to every method of the object, so the helper can update it. - Call
self.maxGain(root). The call updatesself.bestas it goes, so its return value isn't needed here. - Return
self.best. - Declare the helper
maxGain(self, node). - Base case: if
nodeisNone, return 0. An empty subtree adds nothing. - Left gain:
left = max(0, self.maxGain(node.left)). - Right gain:
right = max(0, self.maxGain(node.right)). Both children are processed before the node, because the node needs their answers. - Try this node as the highest point. The path that bends here has the sum
node.val + left + right. Setself.bestto the larger of that and the currentself.best. - Return the one-way gain:
node.val + max(left, right). The parent can extend only one side.
For [-10, 9, 20, None, None, 15, 7] the helper finishes the nodes in this order. Each line shows the node, its left and right gains, the sum of a path bending there, the gain returned, and the best so far:
node 9: left 0, right 0, through 9, gain 9, best 9
node 15: left 0, right 0, through 15, gain 15, best 15
node 7: left 0, right 0, through 7, gain 7, best 15
node 20: left 15, right 7, through 42, gain 35, best 42
node -10: left 9, right 35, through 34, gain 25, best 42
At node 20 the best becomes 42. At the root, -10 + 9 + 35 gives only 34, so the best stays 42, and the returned gain 25 isn't used by anything.
The solution in Python
class Solution:
def maxGain(self, node):
if node is None:
return 0
left = max(0, self.maxGain(node.left))
right = max(0, self.maxGain(node.right))
self.best = max(self.best, node.val + left + right)
return node.val + max(left, right)
def maxPathSum(self, root: Optional[TreeNode]) -> int:
self.best = root.val
self.maxGain(root)
return self.best
Python details:
self.bestis created inmaxPathSum, before the helper first reads it. Python makes an attribute when it is first assigned, so the order of those two lines matters.- Method order doesn't matter.
maxPathSumcan callself.maxGainalthough it is defined above it in the file, because the name is looked up on the object when the call runs. - The built-in
maxtakes any number of arguments and returns the largest. - Recursion depth. Python allows about 1,000 nested calls by default. The tree here is at most 400 levels deep, which fits. A chain of 400 nodes, each with value 1, returns 400.
Complexity
Each node is visited once, with constant work per node, so the time is O(n). The space is the recursion stack, O(h) for a tree of height h, which is O(n) at worst for a chain.
Edge cases and common mistakes
- All values negative.
[-2, -1, -3]returns -1. Startingbestat 0 would wrongly return 0. The one-node tree[-3]returns -3. - Not clamping a child's gain at 0. A negative branch would be added to the sum although leaving it out gives more.
- Returning both sides to the parent. The returned gain is
node.val + max(left, right), notnode.val + left + right. A path can't fork upward. - Assuming the best path passes through the root. In
[-10, 9, 20, None, None, 15, 7]it doesn't. - A skewed tree.
[2, -1]returns 2, since adding -1 only lowers the sum, and[1, -2, 3]returns 4, going 1 then 3 or 3 then 1.
Testing
| tree (level order) | result |
|---|---|
[1, 2, 3] | 6 |
[-10, 9, 20, None, None, 15, 7] | 42 |
[-2, -1, -3] | -1 |
[5] | 5 |
[-3] | -3 |
[2, -1] | 2 |
[1, -2, 3] | 4 |
