Problem overview
The method MaxPathSum receives root, the root of a binary tree with at least one node, and returns the largest path sum of any path in the tree. A path is a sequence of nodes where each is connected 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 the fields val, left and right, and a constructor TreeNode(int x).
- For
[1, 2, 3]the best path is 2, 1, 3 with sum 6. - For
[-10, 9, 20, null, null, 15, 7]the best path is 15, 20, 7 with sum 42. Adding the root would subtract 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
Any path in a tree has a highest node, the one closest to the root, and the path bends there at most once: it goes down the left side, up to that node, and down the right side. So the answer is the best of these "bent at node X" paths over all nodes X. For one node, the best such path is the node's value plus the best downward path on its left plus the best downward path on its right.
That needs one more quantity for each node: the gain, the largest sum of a path that starts at the node and goes down, through one child at a time, or stops at the node itself. A parent can extend only a path that doesn't already bend, so the gain of a node is its value plus the larger of its two children's gains, never both. A path through both children of a node can't also continue up to the node's parent.
Two details matter:
- Negative gains are dropped. If a child's best downward path has a negative sum, including it only lowers the total, so the code treats it as 0, which means "don't go that way".
- The starting value of the answer can't be 0. Every value may be negative, and a path needs at least one node. The answer starts at the root's value and only grows.
The helper computes both quantities in one pass. It first asks the children for their gains, which is a post-order traversal, then updates the answer with the bent path through this node and returns the one-way gain for the parent. Each node is visited once, which gives O(n) time.
Step by step
MaxPathSum
- Keep the best sum in a field of the class,
int best. Every method sees it, so the helper can update it whileMaxPathSumreads it at the end. - Set
best = root.valinMaxPathSum. The root alone is a path, so the answer is at least that. - Call
MaxGain(root). It updatesbestas it walks the tree, so its return value isn't used here. - Return
best.
MaxGain
- Declare
public int MaxGain(TreeNode node). It returns the largest sum of a path that starts atnodeand goes down one side only. - Return 0 when
nodeisnull. An empty subtree adds nothing, and this ends the recursion. - Compute
leftasMath.Max(0, MaxGain(node.left)), the larger of 0 and the left child's gain. - Compute
rightthe same way fornode.right. Both children are processed before this node needs their answers. - Update
bestwithMath.Max(best, node.val + left + right). This is the path that bends at this node. - Return
node.val + Math.Max(left, right), the best one-way path for the parent to extend.
The solution in C#
class Solution {
int best;
public int MaxGain(TreeNode node) {
if (node == null) {
return 0;
}
int left = Math.Max(0, MaxGain(node.left));
int right = Math.Max(0, MaxGain(node.right));
best = Math.Max(best, node.val + left + right);
return node.val + Math.Max(left, right);
}
public int MaxPathSum(TreeNode root) {
best = root.val;
MaxGain(root);
return best;
}
}
The C# details worth knowing:
- A field with no modifier is private.
int best;is a private instance field. Fields start at 0 by default, which is whyMaxPathSumsets it explicitly: the default 0 would be wrong when all values are negative. It also resets the field on each call, so oneSolutionobject can answer several trees. Math.Maxwith capital letters.Math.Max(a, b)returns the larger of two numbers. It lives in theSystemnamespace and has overloads forint,long,doubleand others.intis enough. With at most 30,000 nodes and values between -1000 and 1000, a path sum stays within about 30 million, far below the limit of 2,147,483,647.- Recursion depth. A tree at most 400 levels deep means at most 400 nested calls, which is fine for the default stack. A tree thousands of levels deep could overflow it.
- Lowercase fields. The provided
TreeNodehas lowercaseval,leftandright. C# is case-sensitive, sonode.Valwouldn't compile.
Complexity
Time: O(n). MaxGain is called once for every node, plus once for each missing child, which is at most n + 1 more calls. Each call does a constant amount of work.
Space: O(h), where h is the height of the tree, for the recursion. That is at most 400 here, and in general anywhere from about log n for a balanced tree to n for a chain.
Edge cases and common mistakes
- A single node. The answer is its value, even if negative:
[5]gives 5. - All negative values.
[-2, -1, -3]gives -1, the best single node. Startingbestat 0 would return 0 for this tree, which is not the sum of any path. - A negative child. For
[2, -1]the answer is 2: the child's gain is clamped to 0 and the path is the root alone. - A path that skips the root. In
[-10, 9, 20, null, null, 15, 7]the best path, 15, 20, 7, doesn't include the root. Each node's bent path is checked, not only the root's. - Returning the bent path to the parent. The helper must return
node.val + Math.Max(left, right). Returningnode.val + left + rightwould let a parent extend a path that already bends at the child. - Forgetting to clamp. Without
Math.Max(0, ...), a negative subtree is added into totals it should have been left out of. For[1, -2, 3]the best path is 1, 3 with sum 4, and the -2 must not be part of it.
Testing
[1, 2, 3]gives6.[-10, 9, 20, null, null, 15, 7]gives42.[-2, -1, -3]gives-1.[5]gives5.[2, -1]gives2.[1, -2, 3]gives4.
