Problem
Given a non-empty binary tree, find the maximum path sum. The path may start and end at any nodes.
Example
Input: [-10,9,20,null,null,15,7]
Output: 42Solution
Recursion. At each node, compute the max gain from each subtree (ignore negatives). Update global max with node.val + leftGain + rightGain.
def max_path_sum(root):
max_sum = float('-inf')
def gain(node):
nonlocal max_sum
if not node: return 0
left = max(gain(node.left), 0)
right = max(gain(node.right), 0)
max_sum = max(max_sum, node.val + left + right)
return node.val + max(left, right)
gain(root)
return max_sumfunction maxPathSum(root) {
let maxSum = -Infinity;
function gain(node) {
if (!node) return 0;
const left = Math.max(gain(node.left), 0);
const right = Math.max(gain(node.right), 0);
maxSum = Math.max(maxSum, node.val + left + right);
return node.val + Math.max(left, right);
}
gain(root);
return maxSum;
}class Solution {
int maxSum = INT_MIN;
int gain(TreeNode* node) {
if (!node) return 0;
int left = max(gain(node->left), 0);
int right = max(gain(node->right), 0);
maxSum = max(maxSum, node->val + left + right);
return node->val + max(left, right);
}
public:
int maxPathSum(TreeNode* root) {
gain(root);
return maxSum;
}
};private int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
gain(root);
return maxSum;
}
private int gain(TreeNode node) {
if (node == null) return 0;
int left = Math.max(gain(node.left), 0);
int right = Math.max(gain(node.right), 0);
maxSum = Math.max(maxSum, node.val + left + right);
return node.val + Math.max(left, right);
}Complexity
- Time: O(n)
- Space: O(h)
Explanation
A path through a node uses both children, but a path passed UP can only use one child. We track the global max separately from what we return.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?