Binary Tree Maximum Path Sum: the idea to remember.

The core insight

Return the best nonnegative single branch to the parent, while scoring a path through each node using both child gains.

Why it works

A path continuing to the parent can use at most one child branch. A completed path with this node as its highest node may use both.

The mistake to avoid

Initialize the best answer below every possible node value, and discard negative child gains. Empty paths are not valid final answers.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

int maxPathSum(TreeNode root) {
    int[] best = {Integer.MIN_VALUE}; gain(root, best); return best[0];
}
int gain(TreeNode node, int[] best) {
    if (node == null) return 0;
    int l = Math.max(0, gain(node.left, best)), r = Math.max(0, gain(node.right, best));
    best[0] = Math.max(best[0], node.val + l + r);
    return node.val + Math.max(l, r); // Only one branch can continue upward.
}

Make the next connection