给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
一开始我是这样的思路，从左右子树中获取最大的路径和的值，返回给left,right，然后从left,right,left+right+val,val中取最大值，但是这样会有一个问题，在只有2个节点的树中若值都为负数，那么由于有一个空树，返回的最大值是0会导致最后的结果出错。
看了一些网上的解答，思路都和我差不多，都有共同的错误。查看一些优秀的解答
他是这样的思路：
在递归函数中，如果当前结点不存在，那么直接返回0。否则就分别对其左右子节点调用递归函数，由于路径和有可能为负数，而我们当然不希望加上负的路径和，所以我们和0相比，取较大的那个，就是要么不加，加就要加正数。然后我们来更新全局最大值结果res，就是以左子结点为终点的最大path之和加上以右子结点为终点的最大path之和，还要加上当前结点值，这样就组成了一个条完整的路径。
[LeetCode] Binary Tree Maximum Path Sum 求二叉树的最大路径和 - Grandyang - 博客园
修改我们的程序：
网友评论