Python में दो बाइनरी ट्री के लीफ ट्रैवर्सल के समान होने की जांच कैसे करें?

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

तो, यदि इनपुट है

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

हल करने के चरण

• s1 := एक नई सूची, s2 := एक और नई सूची
• r1 को s1 में और r2 को s2 में डालें
• जब तक s1 और s2 खाली नहीं हैं, तब तक:
  • यदि s1 खाली है या s2 खाली है, तो:
    • False लौटाएं
  • r1_node := s1 का अंतिम नोड, और इसे s1 से हटाएं
  • जब तक r1_node null के समान नहीं है और r1_node लीफ नहीं है, तब तक:
    • यदि r1_node का right null के समान नहीं है, तो:
      • r1_node के right को s1 के अंत में डालें
    • यदि r1_node का left null के समान नहीं है, तो:
      • r1_node के left को s1 के अंत में डालें
      • r1_node := s1 का अंतिम नोड, और इसे s1 से हटाएं
  • r2_node := s2 का अंतिम नोड, और इसे s2 से हटाएं
  • जब तक r2_node null नहीं है और r2_node लीफ नहीं है, तब तक:
    • यदि r2_node का right null नहीं है, तो:
      • r2_node के right को s2 के अंत में डालें
    • यदि r2_node का left null नहीं है, तो:
      • r2_node के left को s2 के अंत में डालें
    • r2_node := s2 का अंतिम नोड, और इसे s2 से हटाएं
  • यदि r1_node null है और r2_node null नहीं है, तो:
    • False लौटाएं
  • यदि r1_node null नहीं है और r2_node null है, तो:
    • False लौटाएं
  • यदि r1_node और r2_node दोनों null नहीं हैं, तो:
    • यदि r1_node का मान r2_node के मान के समान नहीं है, तो:
      • False लौटाएं
• True लौटाएं

उदाहरण

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