A path in a binary tree is a sequence of nodes where each pair of neighbours is joined by an edge, and no node appears twice. The path can start and end anywhere and does not need to pass through the root. Given the root, return the largest possible sum of node values along any non-empty path.
- The number of nodes is in the range 1 to 3 * 10^4
- -1000 <= Node.val <= 1000
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force tries every pair of nodes as path endpoints and sums the path between them, which is O(n^2) or worse. The structure that helps is the same as in Diameter of Binary Tree: each path has a single "peak" node, and through it the best path is node.val + bestDownLeft + bestDownRight, where a negative side is simply skipped (treated as 0). A post-order DFS computes the best downward chain for each node once, and at the same time checks the peak value, so one pass is enough.
Algorithm
- Keep
best = -infinity. - Define
gain(node): return 0 for null. - Compute
l = max(0, gain(node.left))andr = max(0, gain(node.right)). - Update
best = max(best, node.val + l + r)(the path that peaks here). - Return
node.val + max(l, r): a parent can extend only one side.
O(n)Space: O(h) recursion depthbest at negative infinity, not 0. If every value is negative, such as [-3] or [-2,-1], the answer is the largest single node, which is negative.class Solution: def maxPathSum(self, root: Optional[TreeNode]) -> int: best = float("-inf")Β def gain(node): # best sum of a downward chain that starts at node nonlocal best if not node: return 0 l = max(0, gain(node.left)) # skip a negative side r = max(0, gain(node.right)) best = max(best, node.val + l + r) # path that peaks at this node return node.val + max(l, r) # a parent can use only one sideΒ gain(root) return best