Зеркальное отражение узлов двоичного дерева

Постановка задачи

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

Подсказка

  • Первый обход глубины
  • Зеркальное отображение снизу вверх

Попробуйте сами

  • C ++
  • C ++
  • C ++
  • Java
  • Java
  • Python
  • Python
  • JavaScript
  • JavaScript
  • Ruby
  • Ruby
 void mirror_tree (BinaryTreeNode * root) {//TODO: Write - Your - Code} 

Решение

  • C ++
  • ath> C ++
  • путь> C ++
  • Java
  • Java
  • Python
  • Python
  • JavaScript
  • JavaScript
  • Ruby
  • Ruby
 void mirror_tree (BinaryTreeNode * root  ) {если (корень == nullptr) {возврат;  }//Мы выполним обход двоичного дерева после заказа.  если (корень-> слева! = nullptr) {зеркало_дерево (корень-> слева);  } если (корень-> право! = nullptr) {зеркало_дерево (корень-> право);  }//Давайте поменяем местами левый и правый узлы на текущем уровне. BinaryTreeNode * temp = root-> left;  корень-> влево = корень-> вправо;  корень-> right = temp;} int main (int argc, char * argv []) {BinaryTreeNode * root = create_random_BST (15);  display_level_order (корень);  mirror_tree (корень);  cout  

Решение Пояснение

Сложность времени выполнения

Линейный, O (n).

Каждое поддерево должно быть зеркально отражено, чтобы мы посещали каждый узел один раз и отразите поддерево, начинающееся там. Следовательно, сложность времени выполнения равна O (n).

Сложность памяти

Линейная, O (n) в худшем случае.

Анализ решения

Рекурсивное решение имеет сложность памяти O (h) для сбалансированного дерева, так как оно потребляет память в стеке до высоты двоичного дерева. Для перекошенного дерева это может быть O (n).

Здесь мы выполним обход двоичного дерева после заказа. Для каждого узла мы заменим его левый дочерний элемент на его правый дочерний элемент. Исходные узлы показаны зеленым цветом, а узлы, которые были заменены местами, показаны серым. Узел наверху стека (текущий узел) показан голубым цветом. Обратите внимание, что мы выполняем DFS для дерева, т.е. перед возвратом из узла все его дочерние элементы были посещены (и отражены).

Оцените статью
nanomode.ru
Добавить комментарий