题解 | #二叉树的最大路径和#

解法一：深度优先遍历+回溯+全局最优

对于二叉树中的任意节点，若它存在于最大路径中，那么它必属于以下两种情况之一：

1. 作为最优路径的根节点，与其左右子树的最大和相加构成整颗二叉树的最大路径和；
2. 作为最优路径的一部分，与左右子树中最大和更大的那一个一起构成最优路径的一部分，继续向上回溯得到最大路径和。

由于我们其实是不知道哪些节点是在最大和的路径上的。因此，对上面的描述有另一种理解方式：
根据当前节点的角色，路径和可分为两种情况：
一：以当前节点为根节点

1. 只有当前节点
2. 当前节点+左子树
3. 当前节点+右子书
4. 当前节点+左子树+右子树
   这四种情况的最大值即为以当前节点为根的最大路径和
   此最大值要和已经保存的最大值比较，得到整个树的最大路径值
   二：当前节点作为父节点的一个子节点，要和父节点连接的话则需取【单端的最大值】
5. 只有当前节点
6. 当前节点+左子树
7. 当前节点+右子树
   这三种情况的最大值

综上，我们需要保存每个节点对应的以下四个值：当前节点值、当前节点+左子树最大和、当前节点+右子树最大和、当前节点+左子树最大和+右子树最大和。最后取保存的值中的最大值即为所求。

根据上述思路确实可以得到正确的结果，但是在实现的时候我们发现这样做过于繁琐，且内存消耗也比较大（O(N)，N为节点数量）。

因此我们在最终实现的时候使用如下的优化思路：

我们使用贪心的思路，去掉那些和小于0的左右子树，让回溯计算当前路径和的过程变成非递减的过程，这样一来，所有的节点都可以当做处在最大路径和路径上的节点来处理了。

由此，我们可以确定代码的基调：即使用深度优先搜索，先遍历到每个叶子节点，然后向上进行回溯。同时我们需要一个全局变量来保存/比较每次回溯后的【左子树+右子树+当前节点值】。

依照上述思路的代码(python3)如下所示：
时间复杂度为：O(N)，空间复杂度为：O(N)，（递归调用栈）

class Solution:
    def maxPathSum(self , root ):
        # write code here
        self.maxsum = -10000000
        def dfs(root):
            '''
            @param: root TreeNode
            @return int the maxsum of subtree
            '''
            if not root:return 0
            leftsum = max(dfs(root.left),0)
            rightsum = max(dfs(root.right),0)
            self.maxsum = max(self.maxsum,leftsum+rightsum+root.val)
            return max(leftsum,rightsum)+root.val
        dfs(root)
        return self.maxsum