Problem overview
The method maxPathSum receives the root of a binary tree and returns the largest path sum of any path in it. A path is a sequence of nodes where each node is joined to the next by an edge, no node appears twice, and the path has at least one node. It does not have to pass through the root. The path sum is the sum of the node values. The lesson provides the TreeNode class, which has an int val, a TreeNode left and a TreeNode right, and a constructor TreeNode(int x).
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: try every node as the top of the path
Any path in a tree has one highest node, the one closest to the root. The path comes up from one side of that node, passes through it, and goes down the other side. It bends at most once, at that node. So the answer is the best value of "node plus the best downward path on the left plus the best downward path on the right", taken over every node in the tree.
To compute that, a helper maxGain(node) returns the largest sum of a path that starts at node and goes down through one child at a time, or stops at node. Each node needs its children's answers first, so the helper is a recursive depth-first walk that visits each node once.
The helper returns a one-way path, not a path with a bend. The reason is the parent: if a path goes down both sides of a node, it cannot also continue up to the node's parent, because it would have to visit the node twice. So the parent may extend only one side. The two-sided sum is recorded in a field and not returned.
Negative sums are dropped. A child path whose best sum is negative only lowers a total, so the code takes the larger of 0 and the child's result. A 0 means "don't extend in that direction".
Step by step
maxPathSum
- Keep the best sum so far in a field, an
intnamedbest. Every method of the class can see it, so the helper updates it whilemaxPathSumreads it at the end. - Set
best = root.val. The root alone is a path, so the answer is at least its value. Starting at 0 would be wrong when every value is negative. - Call
maxGain(root). It updatesbestas it walks, so its return value isn't needed here. - Return
best.
maxGain
- Declare
int maxGain(TreeNode node). - Return 0 when
nodeisnull. An empty subtree adds nothing, and this is where the recursion stops. - Compute
leftasMath.max(0, maxGain(node.left)). - Compute
rightthe same way withnode.right. Both children are handled before the node itself. - Update
bestwithMath.max(best, node.val + left + right). This treats the node as the top of a path that uses both sides, when they help. - Return
node.val + Math.max(left, right), the best one-way path from this node, for the parent to use.
The solution in Java
class Solution {
int best;
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;
}
}
Java details worth noticing:
- A field shared by two methods.
bestis an instance variable, somaxGaincan update it without returning two values. Java methods return one value only, which is why the two-sided sum travels through a field. Anintfield is 0 until assigned, which is whymaxPathSumsets it explicitly and so also works on aSolutionobject that is reused for another tree. - Recursion depth. The tree is at most 400 levels deep, which the default Java stack handles easily. A chain of 400 nodes, each with value 1, returns 400.
Math.max(int, int)does the clamping to zero. There is no overflow concern: with at most 30,000 nodes and values within 1,000 in absolute value, sums stay below 30,000,000, far inside theintrange.- Null checks come first. Reading
node.valonnullwould throwNullPointerException, so the base case runs before any field is read. InmaxPathSum,root.valis safe because the lesson guarantees at least one node.
Complexity
Time: O(n). maxGain is called once per node and once per missing child, and each call does a constant amount of work.
Space: O(h), where h is the height of the tree: the call stack holds one frame per level. That is at most 400 here, and it is O(log n) for a balanced tree.
Edge cases and common mistakes
- All values negative.
[-2, -1, -3]returns -1 and[-5]returns -5. Startingbestat 0 would return 0 for[-5], which is not the sum of any path. - Not clamping child gains. Without
Math.max(0, ...), the tree[1, -2, 3]returns 3 instead of 4: the best path is 1 then 3, skipping the -2. - Returning the two-sided sum. If
maxGainreturnednode.val + left + right, a parent would extend a path that already bends, and the result could count a path that is not a path. - Assuming the path goes through the root. In
[-10, 9, 20, null, null, 15, 7]the best path, 15, 20, 7, sits entirely in the right subtree. - A single node.
[7]returns 7. Both children arenull, soleftandrightare 0. - A chain.
[1, null, 2, null, 3, null, 4]returns 10. The path simply goes down the chain, and no node has two children. - A node's best path skipping a negative middle. In
[2, -1]the answer is 2: the child's gain is clamped to 0, so the path stays at the root.
Testing
[1, 2, 3]gives6.[-10, 9, 20, null, null, 15, 7]gives42.[-2, -1, -3]gives-1.[-5]gives-5.[1, -2, 3]gives4.[5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1]gives48.[2, -1]gives2.[1, null, 2, null, 3, null, 4]gives10.
