पायथन में बाइनरी ट्री के शीर्ष दृश्य को खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक बाइनरी ट्री है, हमें ट्री का टॉप व्यू ढूंढना है, उन्हें लेफ्ट-टू-राइट सॉर्ट किया जाएगा।

इसलिए, अगर इनपुट इमेज की तरह है, तो आउटपुट [3, 5, 8, 6, 9] होगा, क्योंकि 3 2 से ऊपर है और 5 7 से ऊपर है, इसलिए वे दिखाई नहीं दे रहे हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• देखें:=एक नया खाली नक्शा

• q :=एक डबल एंडेड कतार

• q के अंत में जोड़ी (रूट, 0) डालें

• प्रारंभ:=inf, अंत:=−inf

• जबकि q खाली नहीं है, करें

  • (नोड, कोर्ड) :=q का बायां तत्व, फिर q का बायां तत्व हटा दें

  • प्रारंभ :=न्यूनतम प्रारंभ और समन्वय

  • अंत :=अधिकतम अंत और समन्वय

  • अगर समन्वय नहीं दिख रहा है, तो

    • देखें [समन्वय] :=नोड का मान

  • यदि नोड का बायां भाग शून्य नहीं है, तो

    • q के अंत में (नोड के बाएं, कोर्ड -1) डालें

  • यदि नोड का दायां शून्य नहीं है, तो

    • q के अंत में (नोड का दायां, समन्वय + 1) डालें

• रेस :=एक नई सूची

• क्योंकि मैं रेंज में शुरू से अंत तक, करता हूं

  • अगर मैं देख रहा हूँ, तो

    • रेस के अंत में व्यू [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]