二叉树中的最大路径和

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

深度优先解法：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxPathSum(TreeNode root) {
        int[] ans = {root.val};
        caculateSum(root,ans);
        return ans[0];
    }

    private void caculateSum(TreeNode root,int[] ans){
        if (root == null)
            return;
        caculateSum(root.left,ans);
        caculateSum(root.right,ans);
        int leftVal = root.left == null?0:root.left.val;
        int rightVal = root.right == null ? 0 : root.right.val;

        int curVal = root.val;
        int leftSum = root.val + leftVal;
        int rightSum = root.val + rightVal;
        int allSum = curVal + leftVal + rightVal;
        //三条路选一条最大的
        int tmpMax = Math.max(curVal, Math.max(leftSum, rightSum));
        if (allSum > tmpMax){
            //只能更新最大值，而不能更新当前节点的值
            ans[0] = Math.max(ans[0],allSum);
        }
        //修改当前的节点值
        root.val = tmpMax;
        ans[0] = Math.max(ans[0],tmpMax);
    }
}