Листоподобные деревья

Сложность: 🟢 Легкая

ℹ️ Описание

Дано два бинарных дерева. Все листовые узлы дерева образуют последовательность значений.
Например, для дерева на картинке последовательность значений будет равна (6, 7, 4, 9, 8).

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

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

⚠️ Ограничения

— Количество узлов в каждом дереве находится в диапазоне [1, 200]
— Узлы обоих деревьев имеют значения в диапазоне [0, 200]

✅ Решение

Для решения задачи нам необходимо собрать последовательность всех листовых узлов в обоих деревьях и сравнить их.

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

Функция осуществляет классический обход дерева в глубину DFS (Depth First Search) и когда встречает листовой узел (узел, у которого нет потомков), то добавляет его значение в строку sequence, разделяя значения точкой с запятой. Предварительно мы определяем переменную sequence, равную пустой строке, и управляем ее значением через замыкание.

Вместо строки можно было бы использовать массивы, но после вычисления массивом их пришлось бы сравнивать итерируясь по всем элементам, что дало бы дополнительных k операций. Строки же можно просто сравнить между самой через ==.

Посмотреть реализацию в блоге

#tree #binary_tree #easy