दो पत्तियों के लीफ अनुक्रम समान हैं या नहीं जांचने का पायथन प्रोग्राम

मान लीजिए हमारे पास दो बाइनरी ट्री हैं; हमें जांचना है कि क्या दोनों ट्री में बाएं से दाएं लीफ का अनुक्रम समान है।

उदाहरण के लिए, यदि इनपुट इस तरह है:

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

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

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

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

उदाहरण

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