โปรแกรมค้นหามุมมองด้านบนของไบนารีทรีใน Python

สมมติว่าเรามีไบนารีทรี เราต้องหามุมมองด้านบนของต้นไม้ พวกมันจะถูกจัดเรียงจากซ้ายไปขวา

ดังนั้น หากอินพุตเป็นเหมือนรูปภาพ เอาต์พุตจะเป็น [3, 5, 8, 6, 9] เนื่องจาก 3 อยู่เหนือ 2 และ 5 อยู่เหนือ 7 จึงมองไม่เห็น

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• view :=แผนที่ใหม่เปล่า

• q :=คิวที่สิ้นสุดสองครั้ง

• แทรกคู่ (root, 0) ที่ส่วนท้ายของ q

• start :=inf, end :=−inf

• ในขณะที่ q ไม่ว่างให้ทำ

  • (โหนด, coord) :=องค์ประกอบด้านซ้ายของ q จากนั้นลบองค์ประกอบด้านซ้ายของ q

  • start :=ขั้นต่ำของการเริ่มต้นและ coord

  • end :=สูงสุดของ end และ coord

  • ถ้าไม่ได้มอง coord แล้ว

    • view[coord] :=ค่าของโหนด

  • หากโหนดที่เหลือไม่เป็นโมฆะ

    • แทรก (ด้านซ้ายของโหนด, coord − 1) ที่ส่วนท้ายของ q

  • หากสิทธิ์ของโหนดไม่เป็นโมฆะ

    • แทรก (ด้านขวาของโหนด, coord + 1) ที่ส่วนท้ายของ q

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