Binary Tree Maximum Path Sum
Hard Gain function with global best
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
A path is any sequence of connected nodes, used at most once each, not necessarily through the root. Return the maximum sum of node values on any path.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the largest sum along any path.
Why this works: each node returns its best downward path (one side only). A path that bends at the node uses both sides; update the global best with it.
Example: -10 (9, 20 (15, 7))
at 20: bend 15 + 20 + 7 = 42 (best)return 20 + 15 = 35 upat -10: 9 - 10 + 35 = 34 < 42
✦Hints open one at a time
↗Approach
gain(node) returns node.val + max(0, gain(left), gain(right)) — a path going down one side only. While computing it, update best with node.val + max(0, leftGain) + max(0, rightGain).
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
private int best = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
gain(root);
return best;
}
private int gain(TreeNode n) {
if (n == null) return 0;
int l = Math.max(0, gain(n.left)); // drop negative branches
int r = Math.max(0, gain(n.right));
best = Math.max(best, n.val + l + r); // path bending here
return n.val + Math.max(l, r); // parent can use only one side
}
}!Common mistake
Returning the bent path (both children) to the parent — a parent can only extend a path down one side.
- Time: O(n).
- Space: O(h).