資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：查詢二叉樹中兩節點之間路徑的最大和
假設我們有一個二叉樹，我們需要找到任意兩個節點之間任何路徑的最大和。
所以，如果輸入像
那麼輸出將是 62，因為節點是 [12,13,14,16,7]。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 utils()。它將接收根節點作為引數
如果根節點為空，則
返回 0
l := utils(根節點的左子節點)
r := utils(根節點的右子節點)
max_single := (l 和 r 中的最大值 + 根節點的值) 和 根節點的值 的最大值
max_top := max_single 和 l + r + 根節點的值 的最大值
res := res 和 max_top 的最大值
返回 max_single
從主方法中執行以下操作：
如果根節點為空，則
返回 0
res := 無窮大
utils(根節點)
返回 res
讓我們看看下面的實現以獲得更好的理解：
示例
class TreeNode:
def __init__(self, value):
self.val = value
self.left = None
self.right = None
class Solution:
def solve(self, root):
if root is None:
return 0
self.res = float("-inf")
self.utils(root)
return self.res
def utils(self, root):
if root is None:
return 0
l = self.utils(root.left)
r = self.utils(root.right)
max_single = max(max(l, r) + root.val, root.val)
max_top = max(max_single, l + r + root.val)
self.res = max(self.res, max_top)
return max_single
ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
print(ob.solve(root))輸入
root = TreeNode(13) root.left = TreeNode(12) root.right = TreeNode(14) root.right.left = TreeNode(16) root.right.right = TreeNode(22) root.right.left.left = TreeNode(4) root.right.left.right = TreeNode(7)
輸出
62
更新於: 2020年10月9日
181 次檢視
廣告