124._Binary_Tree_Maximum_Path_Sum.md

124. Binary Tree Maximum Path Sum

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

难度:

Hard

思路

class Solution(object):
    
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.global_max = root.val if root else 0
        self.findmax(root)
        return self.global_max

    def findmax(self, node):
        if not node:
            return 0
        
        left = self.findmax(node.left) 
        left = left if left > 0 else 0
        
        right = self.findmax(node.right)
        right = right if right > 0 else 0
        # 这句是精髓，只要判断出当前这个点作为root的path更长，就更新一下
        self.global_max = max(left + right + node.val, self.global_max) 
        # 这里是因为sub_path只能为一条边，不然跟上面的root组合起来就不是path了
        return max(left, right) + node.val 

其实开始的时候我想当然的用了很傻的方法，并且是错误的，因为这样当[-10,9,20,null,null,15,7]的时候我们会取所有的点，返回41，然而我们可以取到42的， 即15+7+20

class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        if not root.left and not root.right:
            return root.val
        if not root.left:
            return max(root.val, root.val+self.maxPathSum(root.right))
        if not root.right:
            return max(root.val, root.val+self.maxPathSum(root.left))
        return max(root.val, 
                   root.val+self.maxPathSum(root.right), 
                   root.val+self.maxPathSum(root.left), 
                   root.val+self.maxPathSum(root.left)+self.maxPathSum(root.right))