dvenum
@dvenum
python разработчик

Обход Binary-Tree, как сделать быстрее?

На собеседовании попалась задача о сравнении двух последовательности чисел, хранящихся в двух бинарных деревьях. Я затупил, пытаясь сходу изобрести обход с очередью, уже после почесал в голове и смастерил это, но интервьюер говорит, что можно сделать за O(n) на несбалансированных деревьях и нет повода ему не верить.

Сначала у меня рекурсия уходила и в пустые элементы тоже, теперь есть условие, но я не уверен, что это все еще оптимальный вариант. Прочитал главу от Кнута про деревья (Глава 2.3.1), вроде все понятно, но после разгромного интервью я теперь в каждой строке сомневаюсь. Речь именно про минималистичный обход, так то и itertools можно убрать из-за перекопирования элементов, и перехватывать исключения самостоятельно.

import itertools

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def tree_walk(node):
    if node.left:
        yield from tree_walk(node.left)
    yield node.value
    if node.right:
        yield from tree_walk(node.right)

def cmp_tree(node1, node2):
    for v1,v2 in itertools.zip_longest(tree_walk(node1), tree_walk(node2)):
        print(v1, v2)
        if v1 != v2:
            return False

    return True

"""
root1:
1
  2
    3

root2:
    3
  2
1

root3:
  2
1   3
      4
"""

root1 = Node(1)
root1.right = Node(2)
root1.right.right = Node(3)

root2 = Node(3)
root2.left = Node(2)
root2.left.left = Node(1)

root3 = Node(2)
root3.left = Node(1)
root3.right = Node(3)
root3.right.right = Node(4)

print(cmp_tree(root1, root2))
print()
print(cmp_tree(root2, root3))


UPD:
Как выяснилось, код уже с линейной сложностью. Отмечен ответ про сравнение деревьев, см. комментарии глубже.
  • Вопрос задан
  • 116 просмотров
Решения вопроса 1
wataru
@wataru
У вас проблема в решении в том, что вы сравниваете 2 обхода. Это неверно для, как вам уже приводили в пример, этих двух деревьев:
1
 \
  2
   \
    3

    3
   /
  2
 /
1

Тут оба обхода вернут 1,2,3.

Можно в вашем решении добавлять всякие разделители при переходе влево-вправо-вверх. Вставить всякие yeild -1 и другие значения перед походом влево, выводом собственно элемента и походом вправо.

Но есть лучшее решение, через DFS или BFS: вы делайте обход одновременно на двух деревьях. Т.е. у вас параметр функции dfs или в очереди в bfs лежат сразу 2 вершины - по одной из каждого дерева. Вы проверяете, что у них значения одинаковые и что у них у обеих одновременно есть или нет левого и правого ребенка. Потом вызываетесь/кладете в очередь одновременно левых детей и одновременно правых детей. Если в процессе обхода вершины оказались разными, или где-то есть ребенок, а где-то нет - то деревья не равны.

Очень логично реализовывается в виде DFS (ниже псевдокод):
Equals(t1, t2):
   // обработать случай null одного или обоих деревьев.
   return t1.v == t2.v && Equals(t1.left, t2.left) && Equals(t1.right, t2.right)


Все предельно логично - 2 дерева равны, если у них равны корни, левые поддеревья и правые поддеревья.

Кстати, ваше решение, если его исправить, тоже будет за O(n).
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@ayazer
Sr. Software Engineer
1) питон не умеет отбрасывать хвост. Использовать рекурсию я ЯП которые не умееют в хвостовую оптимизацию - так себе идея. Особенно на абстрактной задаче на обход дерева. Особенно если сразу сказали что дерево "сильно несбалансированное". Потому легким движением ваше решение превращается в тыкву.

root1 = Node(1)
cur_node = root1
for i in range (0, 1000):
    cur_node.left = Node(i)
    cur_node = cur_node.left


2) вот эти два дерева у вас выходят одинаковыми. Как графы - да, они одинаковы т.к. симметричны. Как деревья - нет, они разные.
root1 = Node(1)
root1.right = Node(2)
root1.right.right = Node(3)

root2 = Node(3)
root2.left = Node(2)
root2.left.left = Node(1)


Так что сначала нужно пофиксить, а потом уже думать как сделать быстрее
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Poteha Labs Москва
от 100 000 до 160 000 ₽
МТС Москва
от 150 000 до 250 000 ₽
iCode Москва
от 90 000 до 200 000 ₽