https://leetcode.com/problems/binary-tree-maximum-path-sum/
给定一个二叉树，求一个叶子节点到另外一个叶子节点的最大路径和
image.png
int maxDepthRes = Integer.MIN_VALUE;//初始化全局变量，结果为一个最小值
public int maxPathSum(TreeNode root) {
maxPathSumHelper(root);
return maxDepthRes;
}
//注意，第一点：以root为根节点的二叉树，计算最大path，可能经过root节点，也可能不经过root节点
//解释解释，解释这个function
//这个function是计算 以root为根节点，且经过root节点的path的最大值
//注意这个function的return是不能以root为根节点形成半环的
//也就是说 只能是 max(function(root.left),function(root.right)) + root.val
//所以在计算的过程中，有个全局变量maxDepthRes来算最终的最大值，
// 因为：最大path，可能经过root节点，也可能不经过root节点
public int maxPathSumHelper(TreeNode root) {
if (root == null) {
return 0;
}
//递归调用左子树的最大值
int left = Math.max(maxPathSumHelper(root.left), 0);
////递归调用右子树的最大值
int right = Math.max(maxPathSumHelper(root.right), 0);
//left + right + root.val 这个很有意思
//这个值就是以root为衔接点的半环最大值
maxDepthRes = Math.max(maxDepthRes, left + right + root.val);
return Math.max(left, right) + root.val;
}
