python求解二叉树的最大路径和问题

对于求解二叉树的所有路径的时候，是从根节点到任意叶子结点的所有路径，而对于想要求二叉树的最大路径和的问题，并不是从根节点到任意节点的路径和，而是可以从任意一个节点开始，到任意一个节点结束，返回的路径和的值最大，如下给定两颗二叉树：

对于第一颗给定的二叉树的最大路径和返回的值是10，经过的路径可以是从3节点开始，一直遍历到最后一个叶子结点4之间的路径，所得到的路径和最大。

而对于第二颗给定的二叉树的最大路径和返回的值是180，经过的路径节点可以是从80叶节点开始，经过60节点到40叶子节点，所得到的最大路径和的值最大，不经过根节点-30，还有一种可能就是经过根节点-30，但是在算法设计的时候，在遇到-30的时候就会在此节点返回。

针对最大路径和问题中，路径并不一定是从根节点出发一直到叶子节点，而是从任意节点到任意节点这个问题特性，在解决该问题的过程中就会进行判断，判断每一颗子树的当前路径是不是最大路径，所以就需要定义一个最大路径来保存当前的最大路径的值，每一次返回给上层的值都是该节点与其左子树最大路径之和或者是和该节点的右子树的最大路径之和，而且路径是不可以返回的，只能遍历一次，这样方能保证递归过程中返回的当前正在访问的节点的最大路径。

使用python设计算法的代码如下：

class Max: 
    def MaxPath(self, root):
        self.res= float('-inf')
        self.dfs(root)
        return self.res
    def dfs(self, root):
        if not root:
            return 0
        left = max(0, self.dfs(root.left))
        right = max(0, self.dfs(root.right))
        self.res = max(self.res, left + root.val + right)
        return root.val + max(left, right)

这里要注意一个问题，就是关于逆向折回的问题，以上面的第二个图为例子，对于该图的最大路径和事180，其中的60节点的返回给根节点-30的值只有可能是60节点和左叶子结点，或者是60节点和右叶子节点，如下图表示：

但是不可能是将60节点和它的左右子树节点的总值一起返回给-30节点，因为这不是一条路径，存在逆向折回。