पायथन में जांचें कि दो ट्री के सभी लेवल एनाग्राम हैं या नहीं

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

इसलिए, यदि इनपुट इस तरह है:

तो आउटपुट True होगा।

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

• tree_1 पहले ट्री का रूट नोड है और tree_2 दूसरे ट्री का रूट नोड है।
• यदि tree_1 null के समान है और tree_2 null के समान है, तो:
  • True वापस करें
• यदि tree_1 null के समान है या tree_2 null के समान है, तो:
  • False वापस करें
• queue1 := एक नई कतार
• queue2 := एक नई कतार
• tree_1 को queue1 के अंत में डालें
• tree_2 को queue2 के अंत में डालें
• जब तक 1 शून्येतर है, करें:
  • size1 := queue1 का आकार
  • size2 := queue2 का आकार
  • यदि size1 size2 के समान नहीं है, तो:
    • False वापस करें
  • यदि size1 0 के समान है, तो:
    • लूप से बाहर आएं
  • curr_level1 := एक नई सूची
  • curr_level2 := एक नई सूची
  • जब तक size1 > 0, करें:
    • node1 := queue1 का पहला तत्व
    • queue1 से पहला तत्व हटाएं
    • यदि node1 का बायां null के समान नहीं है, तो:
      • node1 के बाएं को queue1 के अंत में डालें
    • यदि node1 का दायां null के समान नहीं है, तो:
      • node1 के दाएं को queue1 के अंत में डालें
    • size1 := size1 - 1
    • node2 := queue2 का पहला तत्व
    • queue2 से पहला तत्व हटाएं
    • यदि node2 का बायां null के समान नहीं है, तो:
      • node2 के बाएं को queue2 के अंत में डालें
    • यदि node2 का दायां null के समान नहीं है, तो:
      • node2 के दाएं को queue2 के अंत में डालें
    • node1 के मान को curr_level1 के अंत में डालें
    • node2 के मान को curr_level2 के अंत में डालें
  • curr_level1 सूची को सॉर्ट करें
  • curr_level2 सूची को सॉर्ट करें
  • यदि curr_level1 curr_level2 के समान नहीं है, तो:
    • False वापस करें
• True वापस करें

उदाहरण

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

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 (True):
        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