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: 遞歸
- 基本思路是自底向上, 最底層的情況, 是本節(jié)點的值+左子節(jié)點的值+右子節(jié)點的值, 去試圖更新最大值
- 然后取出左右子節(jié)點較大的值, 與本節(jié)點一起繼續(xù)往上追溯
- 在追溯到每個節(jié)點的地方, 又可以計算左右子樹最佳路徑累計和，去試圖更新最大值，這個處理邏輯與第一步的處理邏輯重復, 因此可以使用遞歸
- 時間復雜度: ```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
# 選擇較大的一邊, 繼續(xù)往上尋根
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
