Задачи
February 19

Задача. Равенство двоичных деревьев по конечным узлам

Задача: Рассмотрим последовательность конечных узлов бинарного дерева слева направо. Определим равенство двух бинарных деревьев по конечным узлам, если их последовательность конечных значений узлов одинакова.

Напишите алгоритм, который возвращает true, если 2 дерева равным по этому критерию, false - в противном случае.

Примеры:

1е дерево
2е дерево

Output: true

Пояснение: узлы 1го дерева — { 4, 3 }, узлы 2го дерева — { 4, 3 }

Разбор

Алгоритм довольно простой.

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

Реализация

Play-test

https://dotnetfiddle.net/HeLzhd