# LeetCode: 124. 二叉树中的最大路径和¶

## 1、题目描述¶

输入: [1,2,3]

1
/ \
2   3



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

-10
/ \
9  20
/  \
15   7



## 2、解题思路¶

• 得到左子树最大值
• 得到右子树的最大值

• 根+左
• 根+右
• 根+左+右

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def maxPathSum(self, root: TreeNode) -> int:
res = -2**31

def dfs(r):
nonlocal res
if not r:
return 0
max_left = dfs(r.left)
max_right = dfs(r.right)
tmp = max(max_left,max_right,0)+ r.val
res = max(res,max_left+max_right+r.val,tmp)
return tmp
dfs(root)
return res

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.res = -2 ** 31
self.dfs(root)
return self.res

def dfs(self, root: TreeNode):
if not root:
return 0

left = self.dfs(root.left)
right = self.dfs(root.right)

temp = max(left, right, 0) + root.val
self.res = max(self.res, root.val + left + right, temp)
return temp