पायथन में पत्तियों का क्रम दो पत्तियों के समान है या नहीं, यह जांचने के लिए कार्यक्रम

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

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

तब आउटपुट सही होगा क्योंकि दोनों पेड़ों के लिए अनुक्रम [2, 6] है।

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

• c :=एक नई सूची
• एक फ़ंक्शन को परिभाषित करें inorder() । यह जड़ लेगा, और c
• यदि c रिक्त है, तो
  • c :=एक नई सूची
• यदि रूट रिक्त नहीं है, तो
  • इनऑर्डर (रूट के बाएं, c)
  • यदि मूल का बायां भाग रिक्त है और मूल का दायां शून्य है, तो
    • c के अंत में रूट का मान डालें
  • इनऑर्डर (रूट का अधिकार, c)
• वापसी सी
• मुख्य विधि से, निम्न कार्य करें:
• यदि इनऑर्डर(रूट0) इनऑर्डर(रूट1) के समान है, तो
  • सही लौटें
• अन्यथा,
  • झूठी वापसी

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

उदाहरण

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right

class Solution:
   c = []

   def inorder(self, root, c=None):
      if c is None:
         c = []
      if root:
         self.inorder(root.left, c)
         if not root.left and not root.right:
            c.append(root.val)
            self.inorder(root.right, c)
      return c

   def solve(self, root0, root1):
      if self.inorder(root0) == self.inorder(root1):
         return True
      else:
         return False

ob = Solution()
root1 = TreeNode(1)
root1.right = TreeNode(3)
root1.right.left = TreeNode(2)
root1.right.right = TreeNode(6)

root2 = TreeNode(1)
root2.left = TreeNode(3)
root2.right = TreeNode(6)
root2.left.left = TreeNode(2)
print(ob.solve(root1, root2))

इनपुट

root1 = TreeNode(1)
root1.right = TreeNode(3)
root1.right.left = TreeNode(2)
root1.right.right = TreeNode(6) 

root2 = TreeNode(1)
root2.left = TreeNode(3)
root2.right = TreeNode(6)
root2.left.left = TreeNode(2)

आउटपुट

True