Binary Tree Maximum Path Sum

NeetCode: Binary Tree Maximum Path Sum · LeetCode: 124. Binary Tree Maximum Path Sum · Difficulty: Hard

A path is any sequence of connected nodes that visits each node at most once; it doesn't need to include the root. Return the largest possible sum of node values over all non-empty paths.

Example

Text

Input:  [1, 2, 3]                          Output: 6     (2 -> 1 -> 3)
Input:  [-10, 9, 20, null, null, 15, 7]    Output: 42    (15 -> 20 -> 7)

Trees are given in LeetCode's level-order array form: the first value is the root, and each following pair of values holds the left and right child of the next node that exists, in the order the nodes were placed. null marks a missing child, and a missing node has no children listed. The tree(Integer...) helper in each program builds a TreeNode from such an array. TreeNode has the fields val, left, and right; a missing child is null, so no wrapper type is needed. Sums use int: a sum that exceeds the int range wraps silently, and the solution would need long for inputs where that can happen.

Brute force: best path through each node, recomputing gains

The best path that turns at a node uses the node, plus the best downward path into the left (if positive) and into the right (if positive). Compute that for every node, calling a separate gain function that walks the subtree each time.

Java

import java.util.ArrayDeque;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    // Best sum of a path that starts at node and only goes downward.
    private int gain(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return node.val + Math.max(0, Math.max(gain(node.left), gain(node.right)));
    }

    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return Integer.MIN_VALUE;
        }
        int through = root.val + Math.max(0, gain(root.left)) + Math.max(0, gain(root.right));
        return Math.max(through, Math.max(maxPathSum(root.left), maxPathSum(root.right)));
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maxPathSum(tree(1, 2, 3)));
        System.out.println(s.maxPathSum(tree(-10, 9, 20, null, null, 15, 7)));
    }
}

Output

6
42

Time: O(n²) worst case. Space: O(h).

Optimal: one DFS returns the downward gain and records the best turn

Do it in one post-order pass. At each node, get the best downward gain from each child (ignoring negatives with Math.max(0, ...)), update the best sum, kept in a field of Solution, with the "turning" path val + left + right, and return only the single-sided gain val + max(left, right) to the parent, because a path can't fork upward.

Java

import java.util.ArrayDeque;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    private int best;

    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));
        best = Math.max(best, node.val + left + right);
        return node.val + Math.max(left, right);
    }

    public int maxPathSum(TreeNode root) {
        best = Integer.MIN_VALUE;
        dfs(root);
        return best;
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maxPathSum(tree(1, 2, 3)));
        System.out.println(s.maxPathSum(tree(-10, 9, 20, null, null, 15, 7)));
        System.out.println(s.maxPathSum(tree(-3)));
    }
}

Output

6
42
-3

Time: O(n). Space: O(h). Starting best at Integer.MIN_VALUE rather than 0 matters when every value is negative.