資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式：查詢二叉樹的頂部檢視
假設我們有一個二叉樹，我們需要找到樹的頂部檢視，它們將從左到右排序。
因此，如果輸入像圖片一樣，則輸出將為 [3, 5, 8, 6, 9]，因為 3 在 2 的上方，5 在 7 的上方，所以它們不可見。
為了解決這個問題，我們將遵循以下步驟：
view := 一個新的空對映
q := 一個雙端佇列
在 q 的末尾插入 (root, 0) 對
start := inf，end := -inf
當 q 不為空時，執行以下操作：
(node, coord) := q 的左元素，然後移除 q 的左元素
start := start 和 coord 的最小值
end := end 和 coord 的最大值
如果 view 中不存在 coord，則：
view[coord] := node 的值
如果 node 的左子節點不為空，則：
在 q 的末尾插入 (node 的左子節點, coord - 1)
如果 node 的右子節點不為空，則：
在 q 的末尾插入 (node 的右子節點, coord + 1)
res := 一個新的列表
對於從 start 到 end 的範圍內的 i，執行以下操作：
如果 view 中存在 i，則：
在 res 的末尾插入 view[i]
返回 res
讓我們看下面的實現來更好地理解：
示例
from collections import deque
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):
view = {}
q = deque()
q.append((root, 0))
start = float("inf")
end = float("-inf")
while q:
node, coord = q.popleft()
start = min(start, coord)
end = max(end, coord)
if coord not in view:
view[coord] = node.val
if node.left:
q.append((node.left, coord - 1))
if node.right:
q.append((node.right, coord + 1))
res = []
for i in range(start, end + 1):
if i in view:
res.append(view[i])
return res
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.right.left = TreeNode(7)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(2)
root.right.right.right = TreeNode(9)
print(ob.solve(root))輸入
root = TreeNode(5) root.left = TreeNode(3) root.right = TreeNode(8) root.right.left = TreeNode(7) root.right.right = TreeNode(6) root.right.left.left = TreeNode(2) root.right.right.right = TreeNode(9)
輸出
[3, 5, 8, 6, 9]
更新於：2020-12-25
294 次瀏覽
廣告