0124._Binary_Tree_Maximum_Path_Sum.md

124. Binary Tree Maximum Path Sum

难度: Hard

刷题内容

原题连接

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

内容描述

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6
Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(lgN)******

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))