Сравнение структуры и значений двух бинарных деревьев

Условие

Необходимо реализовать функцию, которая:

• принимает два корневых узла типа TreeNode, представляющих два бинарных дерева;
• определяет, совпадают ли оба дерева по форме и значениям узлов;
• возвращает True, если деревья полностью идентичны, и False в остальных случаях.

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

Ответ

Сравнивайте соответствующие пары узлов: два None совпадают, один None означает разную форму, а разные val — разные значения. Затем проверяйте левые и правые поддеревья.

Итеративный вариант не расходует стек вызовов:

def same_tree(first, second):
    stack = [(first, second)]
    while stack:
        left, right = stack.pop()
        if left is None and right is None:
            continue
        if left is None or right is None or left.val != right.val:
            return False
        stack.append((left.left, right.left))
        stack.append((left.right, right.right))
    return True

Два пустых дерева совпадают. Сравниваются именно структура и значения, а не идентичность объектов TreeNode. Время O(n) для совпадающих деревьев; память O(h), где h — высота. Циклические графы не считаются деревьями.