Напишите функцию, которая принимает корневые узлы двух двоичных деревьев и возвращает логическое значение, указывающее, совпадают ли обходы их листьев.

Подход грубой силы будет просто проходить в предварительном порядке оба входных дерева и сохранять конечные узлы в отдельном массиве и, наконец, сопоставлять оба массива результатов, что займет >O(n+m) времени и O ((n+1/2) + (m+1)/2)) пространства, то есть просто количество конечных узлов, которые будет храниться в отдельном массиве. В нашем решении мы увидим, как снизить сложность пространства до высоты дерева, которая представляет собой просто пространство, занимаемое рекурсивным вызовом в стеке вызовов O (час).

В обходе предварительного заказа мы посещаем узел и идем налево, а затем направо, здесь каждый раз, когда мы посещаем узел, мы проверяем, является ли он конечным узлом. и если да, у нас будет некоторая логика для соединения всех листовых узлов, как связанный список.

мы должны удерживать указатель на первый найденный листовой узел, так как нам нужен указатель на начало связанного списка.

Таким образом, мы будем отслеживать Голову, Текущую, Предыдущую.

Мы передадим указатели head и prev обратно нашему родителю, а обновленные указатели от левого дочернего элемента будут переданы правому дочернему элементу.

После обновления связи между предыдущим правым и нашим текущим узлом мы должны обновить предыдущий указатель на текущий узел, так как следующий лист будет использовать его для обновления своей ссылки.

Наконец, мы могли бы перебрать связанный список из обоих бинарных деревьев и посмотреть, равны ли они.

Мы вызываем функцию connect_leaf в обоих входных деревах с начальным заголовком и предыдущими значениями None.

Базовый вариант рекурсии: мы возвращаемся, когда достигаем узла None, и передаем обратно значения head и prev.

Когда мы достигаем узла, у которого левый и правый узлы равны None, у нас есть два условия:

если это первый конечный узел, то мы обновляем указатель начала текущим узлом, в противном случае мы обновляем право предыдущего узла на текущий узел

затем обновите указатель prev на текущий узел.

Для левого дочернего элемента мы используем заголовок и предыдущие указатели, переданные от нашего родителя.

Для правого дочернего элемента мы используем обновленный заголовок и предыдущие указатели, переданные от левого дочернего элемента.

Как только мы получим связанный список указатель на начало из обоих бинарных деревьев, мы пройдемся по ним и посмотрим, равны ли они.

Код доступен здесь.

Временная сложность составляет O(n+m), так как мы имеем два бинарных дерева длины n и m.

Сложность пространства составляет O(h), так как мы используем стек вызовов только для рекурсии.