Binary Tree Maximum Path Sum
HardThe problem
A path is a chain of connected nodes that never visits the same node twice. It does not need to touch the root, and must contain at least one node. Return the biggest possible sum of the values on any path.
- Example 1Input: root = [1, 2, 3]Output: 6
The path 2 → 1 → 3 adds up to 6.
- Example 2Input: root = [-10, 9, 20, null, null, 15, 7]Output: 42
The path 15 → 20 → 7 gives 42. Adding -10 would only make it smaller.
- 1 ≤ number of nodes ≤ 30,000
- -1000 ≤ node value ≤ 1000
- Values can be negative
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
A path can bend at a node, but a parent can only extend a straight leg. Negative legs should be ignored.
The idea
DFS returns the best downward gain (node + max(left,0,right,0)); at each node update the global answer with node + leftGain + rightGain.
Target: O(n) time
Go function shape
func maxPathSum(root *TreeNode) intReference solution
Tested with go test. Try it yourself first, then compare.
// MaxPathSum: a path may bend at one node, but a parent can only extend a straight leg downward.
// Each call returns its best downward leg (ignoring negative legs); the bent path through a node is
// node + left leg + right leg, and the best of those over all nodes is the answer.
func MaxPathSum(root *TreeNode) int {
best := -1 << 60
var leg func(*TreeNode) int
leg = func(n *TreeNode) int {
if n == nil {
return 0
}
l, r := max(leg(n.Left), 0), max(leg(n.Right), 0)
best = max(best, n.Val+l+r)
return n.Val + max(l, r)
}
leg(root)
return best
}