Как сделать сравнение двух бинарных деревьев без рекурсии на языке python?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

from collections import deque

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

def compare_trees(root1, root2):
    if root1 is None and root2 is None:
        return True
    if root1 is None or root2 is None:
        return False

    queue1 = deque([root1])
    queue2 = deque([root2])

    while queue1 and queue2:
        curr1 = queue1.popleft()
        curr2 = queue2.popleft()

        if curr1.val != curr2.val:
            return False

        if curr1.left and curr2.left:
            queue1.append(curr1.left)
            queue2.append(curr2.left)
        elif curr1.left or curr2.left:
            return False

        if curr1.right and curr2.right:
            queue1.append(curr1.right)
            queue2.append(curr2.right)
        elif curr1.right or curr2.right:
            return False

    return not queue1 and not queue2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# Создание двух бинарных деревьев
root1 = TreeNode(1)
root1.left = TreeNode(2)
root1.right = TreeNode(3)

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

# Сравнение деревьев
result = compare_trees(root1, root2)
print(result)  # Вывод: True