image.png
0. 链接
1. 题目
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
2. 思路1: 递归
- 基本思路是自底向上, 最底层的情况, 是本节点的值+左子节点的值+右子节点的值, 去试图更新最大值
- 然后取出左右子节点较大的值, 与本节点一起继续往上追溯
- 在追溯到每个节点的地方, 又可以计算左右子树最佳路径累计和，去试图更新最大值，这个处理逻辑与第一步的处理逻辑重复, 因此可以使用递归
- 时间复杂度: ```O(N)``
- 空间复杂度:
O(logN)
3. 代码
# coding:utf8
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
max_value = None
def check(node):
nonlocal max_value
if node is None:
return 0
left = max(0, check(node.left))
right = max(0, check(node.right))
# 子树要试图成为最大值
if max_value is not None:
max_value = max(max_value, left + right + node.val)
else:
max_value = left + right + node.val
# 选择较大的一边, 继续往上寻根
return max(left, right) + node.val
check(root)
return max_value
solution = Solution()
root1 = node = TreeNode(1)
node.left = TreeNode(2)
node.right = TreeNode(3)
print(solution.maxPathSum(root1))
root2 = node = TreeNode(-10)
node.left = TreeNode(9)
node.right = TreeNode(20)
node.right.left = TreeNode(15)
node.right.right = TreeNode(7)
print(solution.maxPathSum(root2))
root3 = node = TreeNode(-3)
print(solution.maxPathSum(root3))
root4 = node = TreeNode(-2)
node.left = TreeNode(-1)
print(solution.maxPathSum(root4))
root5 = node = TreeNode(-1)
node.left = TreeNode(9)
node.right = TreeNode(20)
node.right.left = TreeNode(15)
node.right.right = TreeNode(7)
print(solution.maxPathSum(root5))
输出结果
6
42
-3
-1
43
4. 结果
image.png
