124. 二叉树中的最大路径和

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

解法一：递归遍历

对于任意一个节点node, 如果最大和路径包含该节点, 那么只可能是两种情况: 1. node的左右子树中所路径和较大的，加上node的值后向node父节点回溯构成最大路径（若向父节点回溯，则左右分支只能选一个，因为不能回路） 2. 左右子树都在最大路径中, 加上node的值构成了最终的最大路径。

naive的思路，（有bug：

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.maxSum = -sys.maxsize
        self.getMax(root)
        return self.maxSum
    
    def getMax(self, root):
        if not root:
            return 0
        left = self.getMax(root.left)
        right = self.getMax(root.right)
        self.maxSum = max(self.maxSum, left+right+root.val)
        return max(left, right) + root.val

这个解法对case[2, -1]失效，返回1而正确答案为2。因为若node的左右子树路径和小于0，对node的贡献就为负，应该不取。

正确解法：

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.maxSum = -sys.maxsize  #用一个全局maxSum记录最大路径和，先预设为最小整数
        self.getMax(root)
        return self.maxSum
    
    def getMax(self, root):
        if not root:
            return 0
        #对左右子树递归
        left = max(0, self.getMax(root.left))  #如果子树路径和为负则应当置0表示最大路径不包含子树
        right = max(0, self.getMax(root.right))
        #判断在该节点包含左右子树的路径和是否大于当前最大路径和
        self.maxSum = max(self.maxSum, root.val + left + right)  
        #注意！该节点对上一层的返回值，只能是该节点值加上左子树（或右子树），因为不可能产生回路
        return root.val + max(left, right)