387，二叉树中的最大路径和
You never want your kids to see you scared. You wanna be that rock that they can grab ahold of in a stormy sea.
当父亲的永远都不想在孩子面前露怯，你想在暴风来临时让他们依靠，成为他们心中的坚石。
问题描述
给定一个非空二叉树，返回其最大路径和。
路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入: [1，2，3]
1
/ \
2 3
输出: 6
示例 2:
输入: [-10，9，20，null，null，15，7]
-10
/ \
9 20
/ \
15 7
输出: 42
问题分析
这道题要求的最大路径和如果是从根节点开始到叶子节点就好办了，我们可以通过递归的方式，从下往上，舍去比较小的路径节点，保留比较大的节点。
但这道题要求的最大路径和并不一定经过根节点，如果再使用上面的方式就行不通了，对于这道题我们可以分为4种情况来讨论
1，只要当前节点，舍弃子节点。比如下面结点2的左右子节点都是负数，如果是负数我们还不如不要，所以直接舍弃子节点。
2，保留当前节点和左子节点。比如下面结点2的右子节点是负数，我们直接舍弃右子节点，但左子节点不是负数，我们可以保留左子节点。
3，保留当前节点和右子节点。比如下面结点2的左子节点是负数，我们直接舍弃左子节点，但右子节点不是负数，我们可以保留右子节点。
4，保留当前节点和两个子节点。比如下面结点2的左右子节点都不是负数，我们都可以留下。
上面的1，2，3都可以作为子树的一部分再继续计算，我们可以使用同一个公式，取左右子节点最大的那个即可，如果都小于0我们不要了，下面公式中left是左子树的值，right是右子树的值
而4是不能在作为子树的一部分参与计算的，因为已经分叉了，比如下面的3→2→4是不能再和结点1进行组合的。第4种情况如果左右子树有一个是小于0的我们还不如不选，如果都大于0我们都要选的。
搞懂了上面的分析过程，代码就很容易写出来了，我们最后来看下代码
代码部分
1private int maxValue = Integer.MIN_VALUE;
2
3public int maxPathSum(TreeNode root) {
4 maxPathSumHelper(root);
5 return maxValue;
6}
7
8public int maxPathSumHelper(TreeNode root) {
9 if (root == null)
10 return 0;
11 //左子节点的值
12 int left = maxPathSumHelper(root.left);
13 //右子节点的值
14 int right = maxPathSumHelper(root.right);
15 //第4种情况
16 int cur = root.val + Math.max(0, left) + Math.max(0, right);
17 //第1,2,3三种情况,返回当前值加上左右子节点的最大值即可，如果左右子节点都
18 //小于0，还不如不选
19 int res = root.val + Math.max(0, Math.max(left, right));
20 //记录最大value值
21 maxValue = Math.max(maxValue, Math.max(cur, res));
22 //第1,2,3种情况还可以再计算，所以返回的是res
23 return res;
24}
●
●
●
●
长按上图，识别图中二维码之后即可关注。
如果喜欢这篇文章就点个"在看"吧