52. Binary Tree Maximum Path Sum

HardTree Binary Tree DFS Dynamic Programming

A path in a binary tree is a sequence of nodes where each consecutive pair is joined by an edge, and no node appears more than once. A path contains at least one node, and it does not need to pass through the root or reach a leaf. Its sum is the total of the values on it.

Given the root of a non-empty binary tree, return the largest possible path sum.

Example 1

Input: root = [2,-1,3]
Output: 5

Explanation: The path 2 → 3 sums to 5. Adding the -1 would only make it smaller.

Example 2

Input: root = [-5,4,8,null,null,-2,6]
Output: 14

Explanation: The best path is 8 → 6. Going through the negative root, 4 → -5 → 8 → 6, only reaches 13.

Example 3

Input: root = [-3]
Output: -3

Explanation: A path must contain at least one node, even if every value is negative.

Constraints

The number of nodes is in the range [1, 3 * 10^4]
-1000 <= Node.val <= 1000

💡 Hint 1

Every path has a single highest node where it "turns". If the turn is at node x, the path is x plus the best downward chain on its left and on its right.

💡 Hint 2

Write a DFS that returns the best downward chain starting at a node: its value plus the better of its two children's chains. If a child's chain is negative, drop it (use 0).

💡 Hint 3

While computing that, try node.val + leftChain + rightChain as a candidate for the overall answer. Start the answer at negative infinity, not 0, so that all-negative trees work.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Post-order DFS where gain(node) returns the best sum of a path that starts at node and goes down into at most one child. Compute the children's gains first and clamp negatives to 0 (it is better to stop than to extend into a losing branch). The best path that turns at node is node.val + leftGain + rightGain; compare it with the global best. Then return node.val + max(leftGain, rightGain) to the parent, because a path going up can only continue down one side. The global best starts at negative infinity (Integer.MIN_VALUE in Java), so a tree of only negative values returns its largest single node.

Time O(n)Space O(h), where h is the tree height

function maxPathSum(root) {
  let best = -Infinity;
  const gain = (node) => {
    if (!node) return 0;
    const left = Math.max(0, gain(node.left));
    const right = Math.max(0, gain(node.right));
    best = Math.max(best, node.val + left + right);
    return node.val + Math.max(left, right);
  };
  gain(root);
  return best;
}

class Solution {
    private int best = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        gain(root);
        return best;
    }

    private int gain(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(0, gain(node.left));
        int right = Math.max(0, gain(node.right));
        best = Math.max(best, node.val + left + right);
        return node.val + Math.max(left, right);
    }
}

/**
 * Definition for a binary tree node (provided):
 * function TreeNode(val, left, right) { this.val = val ?? 0; this.left = left ?? null; this.right = right ?? null; }
 *
 * @param {TreeNode} root
 * @return {number}
 */
function maxPathSum(root) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit