题目描述（困难难度）

考虑一条路径，可以从任意节点开始，每个节点最多经过一次，问经过的节点的和最大是多少。

解法一 递归

参考了 。

首先看到二叉树的题，肯定就是想递归了。递归常规的思路，肯定是递归考虑左子树的最大值，递归考虑右子树的最大值。

问题就来了，怎么考虑包含根节点的最大路径等于多少？因为我们递归求出来的最大 可能不包含根节点的左孩子，例如下边的情况。

所以如果考虑包含当前根节点的 8 的最大路径，首先必须包含左右孩子，其次每次遇到一个分叉，就要选择能产生更大的值的路径。例如下边的例子：

假设我们只考虑通过根节点 8 的最大路径是多少，那么代码就可以写出来了。

接下来我觉得就是这道题最精彩的地方了，现在我们只考虑了包含最初根节点 的路径。那如果不包含当前根节点，而是其他的路径呢？

可以发现在 helper 函数中，我们每次都求了当前给定的节点的左子树和右子树的最大值，和我们 maxPathSum 函数的逻辑是一样的。所以我们利用一个全局变量，在考虑 helper 函数中当前 的时候，同时去判断一下包含当前 root 的路径的最大值。

总

这道题最妙的地方就是在递归中利用全局变量，来更新最大路径的值，太强了。前边遇到过和全局变量结合的递归，例如 106 题，当递归和全局变量结合有时候确实会难理解些。而在 中也应用了和这个题一样的思想，就是发现递归过程和主函数有一样的逻辑，此时可以在递归过程中就可以进行求解。

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^