Корректировка функции сравнения бинарных деревьев

Условие

Проанализировать предоставленный код функции is_equal. Выявить и исправить логические недочёты, которые приводят к неверному определению идентичности двух бинарных деревьев TreeNode. После исправления функция должна возвращать True, только если обе структуры полностью совпадают по расположению узлов и их значениям, в остальных случаях – False.

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

def is_equal(obj_1: TreeNode, obj_2: TreeNode) -> bool:
    if obj_1.val != obj_2.val:
        return False
    if obj_1.left is None and obj_2.left is None:
        left = True
    elif obj_1.left is not None and obj_2.left is not None:
        left = is_equal(obj_1.left, obj_2.left)
    else:
        return False
    if obj_1.right is None and obj_2.right is None:
        right = True
    elif obj_1.right is not None and obj_2.right is not None:
        right = is_equal(obj_1.right, obj_2.right)
    else:
        return False
    return left and right

Ответ

Для непустых корректных деревьев исходная логика уже сравнивает значения и обе ветви. Недостающий случай — None в корне; добавьте его до обращения к val.

def is_equal(first, second):
    if first is None or second is None:
        return first is second
    return (
        first.val == second.val
        and is_equal(first.left, second.left)
        and is_equal(first.right, second.right)
    )

Два пустых дерева равны; одно пустое и одно непустое — нет. Короткое замыкание and прекращает сравнение после первого различия. Время O(n) в случае совпадения, память стека O(h), где h — высота.

Для очень глубокого вырожденного дерева рекурсия может превысить лимит Python: используйте явный стек пар узлов. Циклические структуры не являются обычными бинарными деревьями и требуют иной проверки.