@roxanne.hauck
Для сравнения двух бинарных деревьев без использования рекурсии на языке Python можно использовать алгоритм обхода дерева в ширину или алгоритм обхода дерева в глубину с использованием стека.
Ниже приведен пример алгоритма обхода дерева в ширину:
Ниже приведена реализация данного алгоритма на языке 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 |
В этом примере оба дерева содержат одинаковую структуру и значения узлов, поэтому функция compare_trees возвращает True.