Binary Tree Maximum Path Sum

Share

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge. A node can appear at most once. Given a binary tree, return the maximum path sum of any non-empty path.

Example 1
Input: root=[1,2,3] → Output: 6
Example 2
Input: root=[-10,9,20,null,null,15,7] → Output: 42

Solution Approach

DFS: at each node, compute the max gain from left and right subtrees (only positive contributions count). Update global max with left_gain + root.val + right_gain. Return max single-branch gain to parent.

  • Global maxSum = Integer.MIN_VALUE.
  • dfs(node): if null return 0.
  • leftGain = max(0, dfs(left)), rightGain = max(0, dfs(right)).
  • Update maxSum = max(maxSum, node.val + leftGain + rightGain).
  • Return node.val + max(leftGain, rightGain).
Java
class Solution {
    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxSum;
    }
    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(0, dfs(node.left));
        int right = Math.max(0, dfs(node.right));
        maxSum = Math.max(maxSum, node.val + left + right);
        return node.val + Math.max(left, right);
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(H)