数据结构
网络
关系数据库管理系统 (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 次浏览
广告