जांचें कि क्या दो पेड़ों के सभी स्तर विपर्ययण हैं या नहीं, पायथन में

मान लीजिए, हमें दो बाइनरी ट्री दिए गए हैं। हमें यह जांचना है कि बाइनरी ट्री का प्रत्येक स्तर दूसरे बाइनरी ट्री के समान स्तर का विपर्ययण है या नहीं। यदि यह विपर्यय है तो हम सही लौटते हैं, अन्यथा हम गलत लौटते हैं।

तो, अगर इनपुट पसंद है

, तो आउटपुट ट्रू होगा।

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

• tree_1 पहले पेड़ का रूट नोड है और tree_2 दूसरे पेड़ का रूट नोड है।
• यदि वृक्ष_1 शून्य के समान है और वृक्ष_2 शून्य के समान है, तो
  • सही लौटें
• यदि ट्री_1 अशक्त के समान है या ट्री_2 अशक्त के समान है, तो
  • झूठी वापसी
• कतार1 :=एक नई कतार
• कतार2 :=एक नई कतार
• कतार1 के अंत में ट्री_1 डालें
• कतार2 के अंत में ट्री_2 डालें
• जबकि 1 शून्य नहीं है, करें
  • आकार1 :=कतार1 का आकार
  • आकार2 :=कतार2 का आकार
  • यदि size1 size2 के समान नहीं है, तो
    • झूठी वापसी
  • यदि size1 0 के समान है, तो
    • लूप से बाहर आएं
  • curr_level1 :=एक नई सूची
  • curr_level2 :=एक नई सूची
  • जबकि size1> 0, do
    • नोड1 :=कतार1 का पहला तत्व
    • कतार1 से पहला तत्व हटाएं
    • यदि नोड 1 का बायां भाग शून्य के समान नहीं है, तो
      • कतार1 के अंत में नोड1 के बाईं ओर डालें
    • यदि नोड 1 का अधिकार शून्य के समान नहीं है, तो
      • कतार1 के अंत में नोड1 के दाईं ओर डालें
    • आकार1 :=आकार1 - 1
    • नोड2 :=क्यू 2 का पहला एलिमेंट
    • कतार2 से पहला तत्व हटाएं
    • यदि नोड 2 का बायां भाग शून्य के समान नहीं है, तो
      • कतार2 के अंत में नोड2 के बाईं ओर डालें
    • यदि नोड 2 का अधिकार शून्य के समान नहीं है, तो
      • कतार2 के अंत में नोड2 के दाईं ओर डालें
    • curr_level1 के अंत में नोड1 का मान डालें
    • curr_level2 के अंत में नोड2 का मान डालें
  • सूची को क्रमित करें curr_level1
  • सूची को क्रमित करें curr_level2
  • यदि curr_level1 curr_level2 के समान नहीं है, तो
    • झूठी वापसी
• सही लौटें

उदाहरण

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

def make_tree(elements):
   tree = tree_node(elements[0])
   for element in elements[1:]:
      insert_value(tree, element)
   return tree
def insert_value(temp,value):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if value is not None:
            temp.left = tree_node(value)
         else:
            temp.left = tree_node(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if value is not None:
            temp.right = tree_node(value)
         else:
            temp.right = tree_node(0)
         break
      else:
         que.append(temp.right)
class tree_node:
   def __init__(self, value):
      self.value = value
      self.left = None
      self.right = None
def solve(tree_1, tree_2) :
   if (tree_1 == None and tree_2 == None) :
      return True
   if (tree_1 == None or tree_2 == None) :
      return False
   queue1 = []
   queue2 = []
   queue1.append(tree_1)
   queue2.append(tree_2)
   while (1) :
      size1 = len(queue1)
      size2 = len(queue2)
      if (size1 != size2):
         return False
      if (size1 == 0):
         break
      curr_level1 = []
      curr_level2 = []
      while (size1 > 0):
         node1 = queue1[0]
         queue1.pop(0)
         if (node1.left != None) :
            queue1.append(node1.left)
         if (node1.right != None) :
            queue1.append(node1.right)
         size1 -= 1
         node2 = queue2[0]
         queue2.pop(0)
         if (node2.left != None) :
            queue2.append(node2.left)
         if (node2.right != None) :
            queue2.append(node2.right)
         curr_level1.append(node1.value)
         curr_level2.append(node2.value)
      curr_level1.sort()
      curr_level2.sort()
      if (curr_level1 != curr_level2) :
         return False
   return True
tree_1 = make_tree([5, 6, 7, 9, 8])
tree_2 = make_tree([5, 7, 6, 8, 9])
print(solve(tree_1, tree_2))

इनपुट

[5, 6, 7, 9, 8], [5, 7, 6, 8, 9]

आउटपुट

True