जांचें कि क्या दो बाइनरी ट्री का लीफ ट्रैवर्सल पायथन में समान है

मान लीजिए कि हमारे पास दो बाइनरी ट्री हैं। हमें यह जांचना होगा कि इन दोनों वृक्षों का पत्ता ट्रैवर्सल समान है या नहीं। जैसा कि हम जानते हैं कि लीफ ट्रैवर्सल बायीं ओर से दायें ट्रैवर्स किए गए पत्तों का क्रम है।

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

तब आउटपुट सही होगा क्योंकि दोनों पेड़ों का बायां ट्रैवर्सल क्रम समान है, यानी [5, 7, 8]।

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

• s1:=एक नई सूची, s2:=एक और नई सूची
• r1 को s1 में और r2 को s2 में डालें
• जबकि s1 और s2 खाली नहीं हैं, करें
  • अगर s1 खाली है या s2 खाली है, तो
    • झूठी वापसी
  • r1_node :=s1 का अंतिम नोड, और इसे s1 से हटा दें
  • जबकि r1_node अशक्त के समान नहीं है और r1_node पत्ती नहीं है, करें
    • यदि r1_node का अधिकार शून्य के समान नहीं है, तो
      • s1 के अंत में r1_node के दाईं ओर डालें
    • यदि r1_node का बायां भाग शून्य के समान नहीं है, तो
      • s1 के अंत में r1_node के बाईं ओर डालें
      • r1_node :=s1 का अंतिम नोड, और इसे s1 से हटा दें
  • r2_node :=s2 का अंतिम नोड, और इसे s2 से हटा दें
  • जबकि r2_node रिक्त नहीं है और r2_node पत्ती नहीं है, करें
    • यदि r2_node का अधिकार रिक्त नहीं है, तो
      • s2 के अंत में r2_node के दाईं ओर डालें
    • यदि r2_node का बायां भाग रिक्त नहीं है, तो
      • s2 के अंत में r2_node के बाईं ओर डालें
    • r2_node :=s2 का अंतिम नोड, और इसे s2 से हटा दें
  • यदि r1_node रिक्त है और r2_node रिक्त नहीं है, तो
    • झूठी वापसी
  • यदि r1_node रिक्त नहीं है और r2_node रिक्त है, तो
    • झूठी वापसी
  • यदि r1_node और r2_node दोनों रिक्त नहीं हैं, तो
    • यदि r1_node का मान r2_node के मान के समान नहीं है, तो
      • झूठी वापसी
• सही लौटें

उदाहरण

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

class TreeNode:
   def __init__(self, x):
      self.val = x
      self.left = self.right = None
   def is_leaf(self):
      return self.left == None and self.right == None
def solve(r1, r2):
   s1 = []
   s2 = []
   s1.append(r1)
   s2.append(r2)
   while len(s1) != 0 or len(s2) != 0:
      if len(s1) == 0 or len(s2) == 0:
         return False
      r1_node = s1.pop(-1)
      while r1_node != None and not r1_node.is_leaf():
         if r1_node.right != None:
            s1.append(r1_node.right)
         if r1_node.left != None:
            s1.append(r1_node.left)
            r1_node = s1.pop(-1)
      r2_node = s2.pop(-1)
      while r2_node != None and not r2_node.is_leaf():
         if r2_node.right != None:
            s2.append(r2_node.right)
         if r2_node.left != None:
            s2.append(r2_node.left)
         r2_node = s2.pop(-1)
      if r1_node == None and r2_node != None:
         return False
      if r1_node != None and r2_node == None:
   return False
if r1_node != None and r2_node != None:
if r1_node.val != r2_node.val:
return False
return True
root1 = TreeNode(2)
root1.left = TreeNode(3)
root1.right = TreeNode(4)
root1.left.left = TreeNode(5)
root1.right.left = TreeNode(7)
root1.right.right = TreeNode(8)
root2 = TreeNode(1)
root2.left = TreeNode(6)
root2.right = TreeNode(9)
root2.left.right = TreeNode(5)
root2.right.left = TreeNode(7)
root2.right.right = TreeNode(8)
print(solve(root1, root2))

इनपुट

root1 = TreeNode(2)
root1.left = TreeNode(3)
root1.right = TreeNode(4)
root1.left.left = TreeNode(5)
root1.right.left = TreeNode(7)
root1.right.right = TreeNode(8)
root2 = TreeNode(1)
root2.left = TreeNode(6)
root2.right = TreeNode(9)
root2.left.right = TreeNode(5)
root2.right.left = TreeNode(7)
root2.right.right = TreeNode(8)

आउटपुट

True