Problem overview
The function max_path_sum receives the root of a binary tree as an Option<Box<TreeNode>> and returns the largest sum of any path in it. A path is a sequence of nodes joined by edges, with no node twice and at least one node. It doesn't have to pass through the root. The lesson provides TreeNode, with an i32 field val and the fields left and right, both Option<Box<TreeNode>>.
In the tree with root -10, left child 9, and right child 20 whose children are 15 and 7, the best path is 15, 20, 7, with the sum 42. Continuing up to the root would add -10. When every value is negative, as in the tree -2 with children -1 and -3, the best path is the single node -1.
Approach: every path has a highest node
Any path in a tree has exactly one highest node, the one closest to the root. The path comes up from at most one child of that node and goes down into at most one child, so it bends at most once, there. That suggests trying each node as the highest node and keeping the best result.
For a node, the best path that bends there is the node's value plus the best downward path into its left child plus the best downward path into its right child. A downward path starts at a child and keeps going down, one child at a time, or stops. The helper max_gain computes that value, the best sum of a path that starts at a node and goes down.
Two rules keep it right:
- Ignore negative gains. A side whose best downward path is negative only lowers the total, so it is replaced by 0, which stands for leaving that side out. That is what
.max(0)does. - Return only one side to the parent. A node gives its parent
node.valplus the larger of its two gains. A path that used both sides of the node can't also continue up, because it would then visit the node twice.
For the second example, the helper visits the nodes from the bottom up. Each line shows what it computes at that node:
node 9: left=0 right=0 through=9 best=9 gain=9
node 15: left=0 right=0 through=15 best=15 gain=15
node 7: left=0 right=0 through=7 best=15 gain=7
node 20: left=15 right=7 through=42 best=42 gain=35
node -10: left=9 right=35 through=34 best=42 gain=25
At 20, the path through both children gives 42, which becomes the best. The node returns 35, its value plus its larger side, to the root. At the root, the path through both sides is -10 + 9 + 35 = 34, which doesn't beat 42. The answer is 42.
Step by step
- Create
best. It is alet mutthat starts at the root's value, read withroot.as_ref().unwrap().val.as_reflooks inside theOptionwithout taking the tree, andunwrapis safe because the tree has at least one node. It can't start at 0: if every value is negative, 0 would be a path that doesn't exist. - Run the helper.
Self::max_gain(root, &mut best)updatesbestthrough the mutable borrow while it walks the tree. Its return value isn't needed here. - Return
best. - Write the helper's signature.
max_gaintakesnode: Option<Box<TreeNode>>andbest: &mut i32, and returns ani32, the largest sum of a path that starts atnodeand goes down. - Match on
node. Amatchmust cover both cases of anOption. - Empty subtree. The
Nonearm gives 0, because an empty subtree adds nothing to a path. This is where the recursion stops. - Node arm.
Some(node)binds theBox<TreeNode>, and the innernodetakes the place of the outer one inside the arm. - Gain from the left.
Self::max_gain(node.left, best).max(0), stored inleft. Usingnode.leftmoves the left subtree into the call, which is fine, since nothing needs it again. - Gain from the right, the same way, stored in
right. Both children are processed before the node itself. - Try this node as the highest node. Set
*bestto the larger of*bestandnode.val + left + right.*bestis the variable that the borrowbestpoints to. - Return one side. The arm ends with
node.val + left.max(right), with no semicolon, which is the value of the wholematchand so of the function.
The solution in Rust
impl Solution {
fn max_gain(node: Option<Box<TreeNode>>, best: &mut i32) -> i32 {
match node {
None => 0,
Some(node) => {
let left = Self::max_gain(node.left, best).max(0);
let right = Self::max_gain(node.right, best).max(0);
*best = (*best).max(node.val + left + right);
node.val + left.max(right)
}
}
}
fn max_path_sum(root: Option<Box<TreeNode>>) -> i32 {
let mut best = root.as_ref().unwrap().val;
Self::max_gain(root, &mut best);
best
}
}
Rust details worth knowing:
- Passing
bestdown.bestinmax_gainis already a&mut i32, so the recursive calls pass it as it is, and Rust reborrows it for each call. To read or write the number, the code dereferences it with*best. - A method call on a dereference.
(*best).max(...)needs the parentheses so the dereference happens before the method call.i32::maxreturns the larger of two values. - Moving subtrees.
node.leftandnode.rightare moved out of the box into the recursive calls. After that,nodeis partly moved, but the code still readsnode.val, which is allowed becausevalis ani32that was never moved. - Shadowing in the match. The pattern
Some(node)creates a new variable namednodethat hides the parameter. That is legal and common, but the inner one is aBox<TreeNode>, not anOption. - Method call order.
Self::max_gain(node.left, best).max(0)calls the function first and then.max(0)on itsi32result. - Value of the
match. Both arms are expressions of typei32, and thematchis the last expression of the function.
Complexity
Time: O(n), where n is the number of nodes. Each node is visited once and does a constant amount of work.
Space: O(h), where h is the height of the tree. The only memory besides the tree is the recursion, one call per level, and the lesson limits the depth to 400.
Edge cases and common mistakes
- All values negative. The tree -2 with children -1 and -3 gives -1. This is why
beststarts at the root's value and not at 0, and why the gains are clamped to 0 only for the children, never for the node itself. - A single node. A tree with only the node 5 gives 5, and a tree with only -7 gives -7.
- A path that doesn't use the root. In the example with 42, the best path is entirely in the right subtree.
- Returning both sides to the parent. Returning
node.val + left + rightwould let a parent extend a path that already bends at this node, which would give a route that passes through the node twice. - Forgetting the
max(0). A negative child would be added to the total even though leaving it out is better. - Starting with
best = 0. The answer for an all-negative tree would be 0, which isn't the sum of any path.
Testing
[1, 2, 3]gives 6.[-10, 9, 20, None, None, 15, 7]gives 42.[-2, -1, -3]gives -1.[5]gives 5, and[-7]gives -7.[2, -1]gives 2.[1, -2, 3]gives 4.[5, 4, 8, 11, None, 13, 4, 7, 2, None, None, None, 1]gives 48.
