程序在Python中查找二叉树的顶视图

假设我们有一棵二叉树，我们必须找到树的顶视图，它们将从左到右排序。

因此，如果输入像图像，则输出将为[3、5、8、6、9]，因为3在2之上，而5在7之上，因此它们不可见。

为了解决这个问题，我们将遵循以下步骤-

• 视图：=一个新的空映射

• q：=双头队列

• 在q的末尾插入对(root,0)

• 开始：= inf，结束：= -inf

• 当q不为空时，执行

• 在q的末尾插入（节点的右边，坐标+ 1）

• 在q的末尾插入（节点的左侧，coord − 1）

• view [coord]：=节点值

• （节点，坐标）：= q的左元素，然后删除q的左元素

• 开始：=开始和协调的最小值

• 结束：=结束和协调的最大值

• 如果看不到坐标，则

• 如果节点的左边不为空，则

• 如果节点的权利不为空，则

• res：=一个新列表

• 对于我范围内的开始到结束，

• 在res的末尾插入view [i]

• 如果我认为，那么

• 返回资源

让我们看下面的实现以更好地理解-

示例

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]