Binary Tree Maximum Path Sum

HardTree Binary Tree DFS Dynamic Programming

The walkways of a theme park form a binary tree. Each node is an attraction with a rating, which is negative for attractions with long queues or ongoing construction. A visitor can walk any path: a sequence of attractions in which each consecutive pair is joined by a walkway and no attraction is visited twice. A path contains at least one attraction, and it does not have to pass through the root or end at a leaf.

Given the root of the (non-empty) tree, return the largest total rating that a single path can collect.

Example 1

Input: root = [4,-7,6]
Output: 10

Explanation: The path 4 → 6 collects 10; adding the -7 would only lower the total.

Example 2

Input: root = [-2,9,5,null,null,3,-6]
Output: 15

Explanation: Crossing the negative root pays off here: 9 → -2 → 5 → 3 totals 15.

Example 3

Input: root = [-4,-1,-8]
Output: -1

Explanation: Every rating is negative, so the best path is the single attraction rated -1.

Constraints

The tree has between 1 and 30,000 nodes.
Each rating is an integer from -1000 to 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