算法-二叉树的最大路径和
为了找到二叉树的最大路径和，我们需要考虑所有可能的路径，包括不经过根节点的路径，所以其实如果你从整体上来一条路径一条路径的遍历，太复杂，我们可以换个思路，从每个节点出发，就把那个节点当成根节点，考虑以这个节点为根的最大路径和。这个路径可能只包含左子树或者右子树，或者左右子树都包含。
这里有个很重要的点，当考虑一个节点时，我们实际上只关心以它为根的子树中通过它的最大路径和，不需要知道这条路的完整细节，只需要知道这个最大值是多少。
所以我们用递归和回溯的思想来解决这道题：
-
定义一个辅助函数：该函数将返回以当前节点为根的子树中，通过当前节点的最大单边路径和（即只向左或只向右延伸的最大路径和）以及通过当前节点的最大路径和（可能包括左子树和右子树）。但是，对于全局的最大路径和，我们只需要考虑单边路径和，因为全局最大路径可能不经过根节点。
-
递归逻辑：
- 递归地计算左子树和右子树的最大单边路径和。
- 如果左子树或右子树的最大单边路径和为负，我们可以选择不将其包括在路径中（因为加入负值会降低路径和）。
- 计算通过当前节点的最大路径和（如果左右子树的最大单边路径和都非负，则包括它们；否则，只包括非负的那一边）。
- 更新全局最大路径和（只考虑单边路径和）。
-
回溯：在递归返回之前，需要撤销对当前节点状态的影响，因为我们需要从多个不同的路径来考虑问题。
-
初始化：全局最大路径和初始化为最小整数值（例如，
Integer.MIN_VALUE），因为路径和至少为负数（只有一个负节点时）。但在实际应用中，由于题目说明节点值为0到9，我们可以初始化为比任何可能的单个节点值都小的数，如-1（如果确信树不为空）。 -
返回：返回全局最大路径和
代码如下：
import javax.swing.tree.TreeNode;
public class maxPathSum {
// 二叉树中最大路径和
// 二叉树的路径被定义为一条节点序列，同一个节点在一条路径序列中至多出现一次 该路径至少包含一个节点，且不一定经过根节点
// 返回其最大路径和 注意节点值可能是负数
class Solution{
private int maxSum=Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}
private 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;
// 更新全局最大路径和
maxSum=Math.max(maxSum,priceNewPath);
// 返回以当前节点为根的最大单边路径和
return node.val+Math.max(leftGain,rightGain);
}
}
// 注意maxGain返回的是以当前节点为根的子树中，通过当前节点的最大单边路径和，但这对于找到全局最大路径和是足够的
// 我们不需要知道全局最大路径的确切路径，只需要知道它的和是多少。
}