124. Binary Tree Maximum Path Sum

class Solution {
    private static class ResultHolder {
        private int maxPathSum = Integer.MIN_VALUE;
    }

    public int maxPathSum(TreeNode root) {
        ResultHolder resultHolder = new ResultHolder();
        dfs(resultHolder, root);
        return resultHolder.maxPathSum;
    }

    /**
     * 返回值为以 node 出发的单边路径和
     */
    private int dfs(ResultHolder resultHolder, TreeNode node) {
        if (node == null) {
            return 0;
        }

        int maxLeftSum = Math.max(dfs(resultHolder, node.left), 0);
        int maxRightSum = Math.max(dfs(resultHolder, node.right), 0);
        resultHolder.maxPathSum = Math.max(resultHolder.maxPathSum, maxLeftSum + node.val + maxRightSum);
        return node.val + Math.max(maxLeftSum, maxRightSum); // 注意只能选择一条路径，否则返回的路径和包含多个分叉
    }
}

References

124. Binary Tree Maximum Path Sum
剑指 Offer II 051. 节点之和最大的路径