LeetCode 124. Binary Tree Maximum Path Sum

Posted on In , Views:

🧩 Problem Description

Given the root of a binary tree, return the maximum path sum of the tree.

A path is any sequence of nodes where each pair of adjacent nodes has an edge connecting them.
A path does not need to pass through the root and cannot revisit a node.
The path sum is the sum of node values along the path.

💬 Examples

Example 1

1
2
3
Input: root = [1,2,3]
Output: 6
Explanation: The maximum path is 2 → 1 → 3.

Example 2

1
2
3
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The maximum path is 15 → 20 → 7.

💡 Intuition

At each node, there are two different concepts:

  1. Max Gain to Parent (what we can return upward):
    max(node.val, node.val + leftGain, node.val + rightGain)

    • This represents the best one-side path that can be extended by the parent.

  2. Max Path Through Node (candidate for global answer):
    node.val + max(0, leftGain) + max(0, rightGain)

    • When a path goes through the current node and uses both sides (if beneficial).
    • Negative gains should be treated as 0 (i.e., discard them).

We do a postorder DFS to compute gains bottom-up while maintaining a global maximum.

🔢 Java Code (DFS + Global Tracking)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    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 leftGain = Math.max(0, gain(node.left));
        int rightGain = Math.max(0, gain(node.right));

        // Path that passes through current node using both sides
        int pathThrough = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, pathThrough);

        // Return the max gain to parent: choose one side to extend
        return node.val + Math.max(leftGain, rightGain);
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n) — each node is visited once.
  • Space Complexity: O(h) — recursion stack, where h is the height of the tree (O(n) worst case).

✍️ Summary

  • Use postorder DFS to compute the best upward gain and update a global maximum with the through-node path.
  • Discard negative gains with Math.max(0, ...) so they don’t depress the total.
  • Classic pattern: **“return to parent” vs update global answer.

Related problems

  • lc-543 — Diameter of Binary Tree (length vs sum idea)
  • lc-687 — Longest Univalue Path
  • lc-437 — Path Sum III