UniLecs #162. Равенство бинарных деревьев
UniLecs
Задача: даны два бинарных дерева. Необходимо определить, равны они друг другу или нет. Напоминаем, что одинаковые деревья имеют одинаковое расположение узлов и значений в них.
Входные данные: A - бинарное дерево, B - бинарное дерево
Вывод: true/false
Примеры:
Идея: элегантное и, главное, оптимальное решение данной задачи - это рекурсивный обход дерева.
Давайте рассмотрим алгоритм: два дерева А и В равны друг другу при следующих условиях:
- Значения в корнях одинаковы
- Левое поддерево дерева A равно левому поддереву дерева B
- Правое поддерево дерева A равно правому поддереву дерева B
Воспользуемся поиском в глубину для обоих деревьев одновременно и будем сравнивать значения узлов для каждого уровня.
Реализация:
https://gist.github.com/unilecs/ffc6f85e7598c52691390bad2afe70bf
Play-test: https://dotnetfiddle.net/D6p49X
Решения подписчиков:
- Антон, Rust
https://gist.github.com/AnthonyMikh/897de10c0f366d91a11fb23e682a169d
Play-test: https://play.rust-lang.org/?gist=8d50cea7ce158629c462dcbad064e4e0
2. @Andrsam, Java
https://gist.github.com/andrsam/513f1671a88f8315ede5bc924afbecb6
Play-test: https://repl.it/@andrsam/TreeEqualityTester