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)


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

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

Войти через центр авторизации
Похожие вопросы
МТС Москва
от 150 000 до 250 000 ₽
iCode Москва
от 90 000 до 200 000 ₽
Marilyn Москва
от 100 000 до 130 000 ₽
06 июл. 2020, в 23:49
10000 руб./за проект
06 июл. 2020, в 23:32
35000 руб./за проект