112. Binary Tree Maximum Path Sum

At any node, the best path that passes through it is node.val + max(0, left_gain) + max(0, right_gain). But when returning upward, we can only carry a single branch (left or right), because the parent needs a linear chain to extend.

Approach

DFS returns the best single-branch gain at each node. Meanwhile, at each node, try the "through-node" path and update a global maximum.

class Solution {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) { this.val = val; }
    }

    private int best;

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

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