Pythonで二分木の上面図を見つけるプログラム

二分木があるとすると、木の上面図を見つける必要があり、左から右に並べ替えられます。

したがって、入力が画像のような場合、出力は[3、5、8、6、9]になります。これは、3が2より上で、5が7より上であるため、表示されないためです。

これを解決するには、次の手順に従います-

• ビュー：=新しい空の地図

• q：=両端キュー

• qの最後にペア（ルート、0）を挿入します

• start：=inf、end：=−inf

• qが空でない間、実行します

  • （node、coord）：=qの左側の要素、次にqの左側の要素を削除

  • start：=開始と調整の最小値

  • end：=endとcoordの最大値

  • 座標が表示されていない場合は、

    • view [coord]：=ノードの値

  • ノードの左側がnullでない場合、

    • qの最後に（ノードの左側、座標-1）を挿入します

  • ノードの権利がnullでない場合、

    • qの最後に（ノードの右側、座標+ 1）を挿入します

• res：=新しいリスト

• 範囲内のiの場合、開始から終了まで、実行します

  • 私が表示されている場合は、

    • 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]