資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：查詢節點與其後代之間的差值
假設我們有一棵二叉樹，我們需要找到任何節點與其後代之間最大的絕對差值。
因此，如果輸入類似於
那麼輸出將是 7，因為最大的絕對差值是在節點 8 和 1 之間。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式 dfs()。這將接收節點作為引數。
- 如果節點不為空，則
- 返回一個包含正無窮大和負無窮大的列表。
- left := dfs(節點的左子節點)
- right := dfs(節點的右子節點)
- res := 一對值 (left[0]、right[0] 和節點值的最小值，以及 left[1]、right[1] 和節點值的最大值)
- ans := ans、(節點值 - res[0]) 和 (res[1] - 節點值) 中的最大值
- 返回 res
- 從主方法中執行以下操作：
- ans := 0
- dfs(根節點)
- 返回 ans
讓我們看看下面的實現來更好地理解：
示例
class TreeNode:
def __init__(self, data, left = None, right = None):
self.val = data
self.left = left
self.right = right
class Solution:
def solve(self, root):
def dfs(node):
if not node:
return [float("inf"), float("-inf")]
left = dfs(node.left)
right = dfs(node.right)
res = [min(left[0], right[0], node.val), max(left[1], right[1], node.val)]
self.ans = max(self.ans, node.val - res[0], res[1] - node.val)
return res
self.ans = 0
dfs(root)
return self.ans
ob = Solution()
root = TreeNode(1)
root.left = TreeNode(5)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(8)
root.right.left.left = TreeNode(7)
root.right.left.right = TreeNode(4)
print(ob.solve(root))輸入
root = TreeNode(1) root.left = TreeNode(5) root.right = TreeNode(3) root.right.left = TreeNode(2) root.right.right = TreeNode(8) root.right.left.left = TreeNode(7) root.right.left.right = TreeNode(4)
輸出
7
更新於: 2020年11月19日
103 次瀏覽
廣告