पता करें कि बाइनरी ट्री का दिया गया वर्टिकल लेवल पायथन में सॉर्ट किया गया है या नहीं

मान लीजिए कि हमारे पास बाइनरी ट्री है; हमें यह जांचना है कि बाइनरी ट्री का दिया गया वर्टिकल लेवल सॉर्ट किया गया है या नहीं। जब दो नोड्स ओवरलैप हो रहे हों, तो जांचें कि वे जिस स्तर से संबंधित हैं, उसी क्रम में क्रमबद्ध हैं।

तो, अगर इनपुट l =-1 जैसा है

तब आउटपुट ट्रू होगा, क्योंकि लेवल -1 में एलिमेंट 3,7 हैं और उन्हें सॉर्ट किया गया है।

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

• अगर रूट शून्य है, तो

  • सही लौटें

• पिछला_मान :=-इन्फ़

• current_level :=0

• current_node :=मान 0 के साथ एक नया ट्री नोड

• q नामक एक dequeue परिभाषित करें

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

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

  • current_node :=q[0, 0]

  • current_level :=q[0, 1]

  • q के बाएँ से तत्व हटाएं

  • अगर current_level स्तर के समान है, तो

    • अगर पिछला_मान <=current_node.val, तो

      • पिछला_मान :=current_node.val

    • अन्यथा,

      • झूठी वापसी

  • अगर current_node.left शून्य नहीं है, तो

    • q के अंत में (current_node.left, current_level - 1) डालें

  • अगर current_node.right गैर-शून्य है, तो

    • q के अंत में (current_node.right, current_level + 1) डालें

• सही लौटें

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

from collections import deque
from sys import maxsize
INT_MIN = -maxsize
class TreeNode:
   def __init__(self, key):
      self.val = key
      self.left = None
      self.right = None
def are_elements_sorted(root, level):
   if root is None:
      return True
   previous_value = INT_MIN
   current_level = 0
   current_node = TreeNode(0)
   q = deque()
   q.append((root, 0))
   while q:
      current_node = q[0][0]
      current_level = q[0][1]
      q.popleft()
      if current_level == level:
         if previous_value <= current_node.val:
            previous_value = current_node.val
         else:
            return False
      if current_node.left:
         q.append((current_node.left, current_level - 1))
      if current_node.right:
         q.append((current_node.right, current_level + 1))
   return True
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(8)
root.left.right = TreeNode(5)
root.left.right.left = TreeNode(7)
level = -1
print(are_elements_sorted(root, level))

इनपुट

root = TreeNode(2) root.left = TreeNode(3) root.right = TreeNode(6)
root.left.left = TreeNode(8) root.left.right = TreeNode(5)
root.left.right.left = TreeNode(7)

आउटपुट

True