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

     给定一个非空二叉树，返回其最大路径和。

     本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

     示例 1:

     输入: [1,2,3]

        1
       / \
      2   3
     

     输出: 6
     示例 2:

     输入: [-10,9,20,null,null,15,7]

     -10
     /
     9 20
     /
     15 7

     输出: 42

     思路：一般情况下最大的路径是由一个点的左路径和右路径加起来的，因此可以采用dfs的方法。注意要考虑到负数。

class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.curr_max = float(’-inf’)
def getMax(root):
if root == None:
return 0
left = max(0,getMax(root.left))
right = max(0,getMax(root.right))
self.curr_max = max(self.curr_max , left + right + root.val)
return max(left,right)+root.val
getMax(root)
return self.curr_max