力扣HOT100 - 124. 二叉树中的最大路径和

解题思路：

class Solution {
    int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return max;
    }

    public int maxGain(TreeNode node) {
        if (node == null) return 0;

        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        int priceNewPath = node.val + leftGain + rightGain;
        max = Math.max(priceNewPath, max);

        return node.val + Math.max(leftGain, rightGain);
    }
}