Chương trình tìm chế độ xem trên cùng của cây nhị phân trong Python

Giả sử chúng ta có một cây nhị phân, chúng ta phải tìm hình chiếu trên cùng của cây, chúng sẽ được sắp xếp từ trái sang phải.

Vì vậy, nếu đầu vào giống như hình ảnh, thì đầu ra sẽ là [3, 5, 8, 6, 9], vì 3 ở trên 2 và 5 ở trên 7 nên chúng không được nhìn thấy.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• view:=một bản đồ trống mới

• q:=một hàng đợi kết thúc kép

• chèn cặp (gốc, 0) vào cuối q

• start:=inf, end:=−inf

• trong khi q không trống, thực hiện

  • (node, coord):=phần tử bên trái của q, sau đó xóa phần tử bên trái của q

  • start:=tối thiểu của start và coord

  • end:=tối đa của kết thúc và kết hợp

  • nếu coord không được xem, thì

    • view [coord]:=giá trị của nút

  • nếu bên trái của nút không rỗng, thì

    • insert (bên trái của nút, coord - 1) vào cuối q

  • nếu bên phải của nút không rỗng, thì

    • insert (bên phải của nút, coord + 1) vào cuối q

• res:=một danh sách mới

• đối với tôi trong phạm vi bắt đầu đến kết thúc, hãy làm

  • nếu tôi đang ở trong tầm nhìn, thì

    • chèn chế độ xem [i] vào cuối res

• trả lại res

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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)

Đầu ra

[3, 5, 8, 6, 9]