Problem
Given the root of a binary tree, return the maximum path sum of any non-empty path. A path can start and end at any node, but each node can be used at most once.Example(s)
Consider the following example(s) to understand the expected input and output.Input
root = [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
Output
42Solution
This solution uses Depth-First Search (DFS) with recursion. For each node, we calculate the maximum path sum that can be extended upward to its parent.A negative path would only decrease the total sum, so any negative contribution from the left or right subtree is ignored.
At every node, we also calculate a path that passes through the current node by combining the maximum contribution from both the left and right subtrees. This path is a possible answer, so the global maximum is updated.
Only one side can be extended to the parent because a valid path cannot branch in two directions after moving upward.
class Solution {
private int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}
private int maxGain(TreeNode node) {
if (node == null) {
return 0;
}
// Ignore negative paths.
int leftGain = Math.max(0, maxGain(node.left));
int rightGain = Math.max(0, maxGain(node.right));
// Best path passing through the current node.
int currentPath = node.val + leftGain + rightGain;
maxSum = Math.max(maxSum, currentPath);
// Return the best path that can extend to the parent.
return node.val + Math.max(leftGain, rightGain);
}
}
Complexity
Each node is visited exactly once, resulting in a time complexity ofO(n).
The recursive call stack can grow up to the height of the tree, resulting in an extra space complexity of
O(h), where h is the height of the tree.