পাইথনে একটি বাইনারি গাছের শীর্ষ দৃশ্য খুঁজে পাওয়ার জন্য প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি গাছ আছে, আমাদের গাছের উপরের দৃশ্যটি খুঁজে বের করতে হবে, সেগুলিকে বাম থেকে ডানে সাজানো হবে।

সুতরাং, যদি ইনপুটটি ছবির মতো হয়, তাহলে আউটপুট হবে [3, 5, 8, 6, 9], যেহেতু 3 2 এর উপরে এবং 5 7 এর উপরে তাই তারা দৃশ্যমান নয়৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• দেখুন :=একটি নতুন খালি মানচিত্র

• q :=একটি ডবল শেষ সারি

• q

  এর শেষে জোড়া (root, 0) সন্নিবেশ করান

• শুরু :=inf, শেষ :=−inf

• q খালি না থাকার সময়, করুন

  • (নোড, কর্ড) :=q এর বাম উপাদান, তারপর q এর বাম উপাদান সরিয়ে দিন

  • শুরু :=ন্যূনতম সূচনা এবং সমন্বয়

  • শেষ :=সর্বাধিক প্রান্ত এবং কোর্ড

  • যদি coord দেখা না হয়, তাহলে

    • দেখুন[coord] :=নোডের মান

  • যদি নোডের বাম অংশ শূন্য না হয়, তাহলে

    • q

      -এর শেষে সন্নিবেশ করুন (নোডের বামে, coord −1)

  • যদি নোডের ডানদিকে শূন্য না হয়, তাহলে

    • q

      এর শেষে সন্নিবেশ করুন (নোডের ডানদিকে, coord + 1)

• res :=একটি নতুন তালিকা

• আমি পরিসীমা শুরু থেকে শেষ করার জন্য, করুন

  • যদি আমি দেখতে পাই, তাহলে

    • res এর শেষে ভিউ[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]