Инвертирование дерева
Задан массив целых чисел. Создайте из них Бинарное Дерево Поиска. Если вставляемое значение равно текущей вершине, то его следует вставлять в правое поддерево.
Реализуйте метод InvertTree , который инвертирует бинарное дерево.
Напишите код согласно следующего интерфейса:
TreeNode(int x) : val(x), left(NULL), right(NULL) <>
void Insert(int val); // Вставка числа val в Бинарное Дерево Поиска
void InOrder(void); // Выведите элементы Бинарного Дерева Поиска при InOrder обходе
void InvertTree(void); // Инвертирование Бинарного Дерева Поиска
Вы можете создавать (использовать) по необходимости дополнительные методы.
Входные данные
Первая строка содержит число n ( 1 ≤ n ≤ 100 ). Вторая строка содержит n целых чисел.
Выходные данные
Создайте Бинарное Дерево Поиска из входных данных. Инвертируйте дерево используя метод InvertTree . Выведите элементы Бинарного Дерева Поиска после инвертирования используя метод InOrder .
Анализ алгоритма
Если root = NULL, то инвертированным для пустого дерева будет пустое.
Далее для каждой вершины следует переставить местами левого и правого сына. То есть root -> left присвоить инвертированное правое поддерево, а root -> right присвоить инвертированное левое поддерево .
TreeNode* invertTree(TreeNode* root)
if (root == NULL) return root;
TreeNode* temp = root->left;
Java реализация
public class Solution
public TreeNode invertTree(TreeNode root)
if (root == null) return root;
TreeNode temp = root.left;
Задача: инвертируем бинарное дерево
Решаем задачи, которые дают программистам на собеседованиях в IT-компаниях. Сегодня инвертируем бинарное дерево.
Иллюстрация: Polina Vari для Skillbox Media
Дмитрий Зверев
Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.
Сергей Голицын
Senior Java Developer в Covalent Inc. и преподаватель. Больше семи лет в Java-разработке. В свободное время судит хакатоны и делится опытом с начинающими программистами. Пишет статьи для «Хабра» и Medium. Ведёт телеграм-каналы «Полезные ссылки около Java» и Cracking code interview.
Условие. Дан массив узлов бинарного дерева — root. Нужно инвертировать дерево и вернуть полученный массив. Инвертировать бинарное дерево — значит сделать так, чтобы слева от главного узла были значения больше него, а справа — меньше. Когда значения равны, их можно помещать с любой стороны.
Ввод и вывод. Пример 1
Ввод: root = [2,1,3] Вывод: [2,3,1]
Ввод и вывод. Пример 3
Ввод: root = [] Вывод: []
Решить эту задачу самостоятельно и на разных языках программирования можно на LeetCode. Наше решение взято из Telegram-канала Сергея Cracking code interview.
Решение
Чтобы решить эту задачу, мы должны поменять все левые и правые элементы местами и сделать это в обратном порядке — с помощью рекурсии.
Начнём с самого верхнего узла и будем двигаться вниз — до самого нижнего. Каждый раз, когда мы заходим на очередной узел, меняем левый и правый элементы местами. А когда узлы закончатся, возвращаем полученный массив.
Полный алгоритм такой:
- На входе мы получаем узел бинарного дерева — root.
- Проверяем: если root — это пустой массив или null, то возвращаем null.
- Если нет: вызываем рекурсию на левый узел, а затем на правый.
- После того как обе рекурсии вернули результаты, меняем левый и правый узлы местами.
- Возвращаем корень дерева.
Вот как этот алгоритм будет реализован на Java:
public TreeNode invertTree(TreeNode root) < if(root == null)< return null; > TreeNode left = invertTree(root.left); TreeNode right = invertTree(root.right); root.left = right; root.right = left; return root; > >
Временная сложность: O(n) — так как мы перебирали все элементы массива.
Ёмкостная сложность: O(1) — нам нужно заранее определённое количество места в памяти (максимальный размер памяти — размер массива бинарного дерева).
Читайте также:
- Задача: проверить строки на изоморфность
- Тест. Какой язык создадите вы — Java или Python?
- Рекурсия вокруг нас: люди, соборы и капуста романеско
Инвертировать альтернативные уровни идеального бинарного дерева
Напишите эффективный алгоритм инвертирования альтернативных уровней идеального бинарного дерева.
Например, рассмотрим следующее дерево:
Мы должны преобразовать его в следующее дерево:
1. Использование обхода по уровням
Идея состоит в том, чтобы выполнить обход порядка уровней идеального бинарного дерева и последовательно обходим его узлы. Затем для каждого нечетного уровня поместите все узлы, присутствующие на этом уровне, в stack. Наконец, в конце каждого нечетного уровня мы помещаем узлы, присутствующие в stack, в их правильное положение. Ниже приведена программа на C++, Java и Python, которая демонстрирует это:
C++
using namespace std ;
// Структура данных для хранения узла бинарного дерева
struct Node
Node * left , * right ;
Node ( int data )
this -> data = data ;
this -> left = this -> right = nullptr ;
// Функция для вывода обхода идеального бинарного дерева по порядку уровней
void levelOrderTraversal ( Node * root )
if ( root == nullptr ) <
// создаем пустую queue и ставим в queue корневой узел
queue < Node * >queue ;
queue . push ( root ) ;
// указатель для хранения текущего узла
Node * curr = nullptr ;
// цикл до тех пор, пока queue не станет пустой
while ( queue . size ( ) )
// обрабатываем каждый узел в очереди и ставим в queue их
// непустые левый и правый потомки
curr = queue . front ( ) ;
queue . pop ( ) ;
if ( curr -> left ) <
queue . push ( curr -> left ) ;
if ( curr -> right ) <
queue . push ( curr -> right ) ;
// Итерационная функция для инвертирования альтернативных уровней идеального бинарного дерева
// использование обхода порядка уровней
void invertBinaryTree ( Node * root )
// базовый случай: если дерево пусто
if ( root == nullptr ) <
// поддерживаем queue и ставим в queue корневой узел
q . push ( root ) ;
// для хранения информации о текущем уровне
bool level = false ;
// поддерживать другую queue для хранения узлов, присутствующих на нечетном уровне
queue < Node * >level_nodes ;
// поддерживать stack для хранения данных узла на нечетном уровне
stack < int >level_data ;
// цикл до тех пор, пока queue не станет пустой
while ( ! q . empty ( ) )
// получаем размер текущего уровня
int n = q . size ( ) ;
// обрабатываем все узлы, присутствующие на текущем уровне
// удалить передний узел из очереди
Node * curr = q . front ( ) ;
// если уровень нечётный
// поставить текущий узел в queue
level_nodes . push ( curr ) ;
// помещаем данные текущего узла в stack
level_data . push ( curr -> data ) ;
// если текущий узел является последним узлом уровня
// перевернуть уровень
level = ! level ;
// помещаем элементы, присутствующие в `level_data`, в их правильные
// позиция с использованием `level_nodes`
while ( ! level_nodes . empty ( ) )
Node * front = level_nodes . front ( ) ;
front -> data = level_data . top ( ) ;
level_nodes . pop ( ) ;
level_data . pop ( ) ;
// поставить в queue левый дочерний элемент текущего узла
if ( curr -> left ) <
q . push ( curr -> left ) ;
// ставим в queue правого дочернего элемента текущего узла
if ( curr -> right ) <
q . push ( curr -> right ) ;
/* Построим следующее дерево
8 9 10 11 12 13 14 15
Node * root = new Node ( 1 ) ;
root -> left = new Node ( 2 ) ;
root -> right = new Node ( 3 ) ;
root -> left -> left = new Node ( 4 ) ;
root -> left -> right = new Node ( 5 ) ;
root -> right -> left = new Node ( 6 ) ;
root -> right -> right = new Node ( 7 ) ;
root -> left -> left -> left = new Node ( 8 ) ;
root -> left -> left -> right = new Node ( 9 ) ;
root -> left -> right -> left = new Node ( 10 ) ;
root -> left -> right -> right = new Node ( 11 ) ;
root -> right -> left -> left = new Node ( 12 ) ;
root -> right -> left -> right = new Node ( 13 ) ;
root -> right -> right -> left = new Node ( 14 ) ;
root -> right -> right -> right = new Node ( 15 ) ;
invertBinaryTree ( root ) ;
levelOrderTraversal ( root ) ;
результат:
1 3 2 4 5 6 7 15 14 13 12 11 10 9 8
Java
import java . util . ArrayDeque ;
import java . util . Queue ;
import java . util . Stack ;
// Класс для хранения узла бинарного дерева
class Node
Node left , right ;
Node ( int data ) <
this . data = data ;
class Main
// Функция для вывода обхода идеального бинарного дерева по порядку уровней
public static void levelOrderTraversal ( Node root )
if ( root == null ) <
// создаем пустую queue и ставим в queue корневой узел
Queue
queue . add ( root ) ;
// для сохранения текущего узла
Node curr = null ;
// цикл до тех пор, пока queue не станет пустой
while ( ! queue . isEmpty ( ) )
// обрабатываем каждый узел в очереди и ставим в queue их
// непустые левый и правый потомки
curr = queue . poll ( ) ;
System . out . print ( curr . data + » » ) ;
if ( curr . left != null ) <
queue . add ( curr . left ) ;
if ( curr . right != null ) <
queue . add ( curr . right ) ;
// Итерационная функция для инвертирования альтернативных уровней идеального бинарного дерева
// использование обхода порядка уровней
public static void invertBinaryTree ( Node root )
// базовый случай: если дерево пусто
if ( root == null ) <
// поддерживаем queue и ставим в queue корневой узел
Queue
q . add ( root ) ;
// для хранения информации о текущем уровне
boolean level = false ;
// поддерживать другую queue для хранения узлов, присутствующих на нечетном уровне
Queue
// поддерживать stack для хранения данных узла на нечетном уровне
Stack
// цикл до тех пор, пока queue не станет пустой
while ( ! q . isEmpty ( ) )
// получаем размер текущего уровня
int n = q . size ( ) ;
// обрабатываем все узлы, присутствующие на текущем уровне
while ( n — > 0 )
// удалить передний узел из очереди
Node curr = q . poll ( ) ;
// если уровень нечётный
// поставить текущий узел в queue
level_nodes . add ( curr ) ;
// помещаем данные текущего узла в stack
level_data . add ( curr . data ) ;
// если текущий узел является последним узлом уровня
// перевернуть уровень
level = ! level ;
// помещаем элементы, присутствующие в `level_data`, в их правильные
// позиция с использованием `level_nodes`
while ( ! level_nodes . isEmpty ( ) )
Node front = level_nodes . poll ( ) ;
front . data = level_data . pop ( ) ;
// поставить в queue левый дочерний элемент текущего узла
if ( curr . left != null ) <
q . add ( curr . left ) ;
// ставим в queue правого дочернего элемента текущего узла
if ( curr . right != null ) <
q . add ( curr . right ) ;
public static void main ( String [ ] args )
/* Построим следующее дерево
8 9 10 11 12 13 14 15
Node root = new Node ( 1 ) ;
root . left = new Node ( 2 ) ;
root . right = new Node ( 3 ) ;
root . left . left = new Node ( 4 ) ;
root . left . right = new Node ( 5 ) ;
root . right . left = new Node ( 6 ) ;
root . right . right = new Node ( 7 ) ;
root . left . left . left = new Node ( 8 ) ;
root . left . left . right = new Node ( 9 ) ;
root . left . right . left = new Node ( 10 ) ;
root . left . right . right = new Node ( 11 ) ;
root . right . left . left = new Node ( 12 ) ;
root . right . left . right = new Node ( 13 ) ;
root . right . right . left = new Node ( 14 ) ;
root . right . right . right = new Node ( 15 ) ;
invertBinaryTree ( root ) ;
levelOrderTraversal ( root ) ;
результат:
1 3 2 4 5 6 7 15 14 13 12 11 10 9 8
Python
from collections import deque
# Класс для хранения узла бинарного дерева.
class Node :
def __init__ ( self , data , left = None , right = None ) :
self . data = data
self . left = left
self . right = right
# Функция для печати обхода по уровням идеального бинарного дерева
def levelOrderTraversal ( root ) :
if root is None :
# создает пустую queue и ставит в queue корневой узел
queue = deque ( )
queue . append ( root )
# Цикл # до тех пор, пока queue не станет пустой
while queue :
# обрабатывает каждый узел в очереди и ставит их в queue.
# непустые левый и правый потомки
curr = queue . popleft ( )
print ( curr . data , end = ‘ ‘ )
if curr . left :
queue . append ( curr . left )
if curr . right :
queue . append ( curr . right )
# Итерационная функция для инвертирования альтернативных уровней идеального бинарного дерева
# с обходом по уровням
def invertBinaryTree ( root ) :
# Базовый случай: если дерево пусто
if root is None :
# поддерживает queue и ставит в queue корневой узел
q . append ( root )
# для хранения информации о текущем уровне
level = False
# поддерживает другую queue для хранения узлов, присутствующих на нечетном уровне.
level_nodes = deque ( )
# поддерживает stack для хранения данных узла на нечетном уровне.
level_data = deque ( )
# Цикл # до тех пор, пока queue не станет пустой
# получить размер текущего уровня
size = len ( q )
# обрабатывает все узлы, присутствующие на текущем уровне.
for n in reversed ( range ( size ) ) :
# Передний узел удаления из очереди
curr = q . popleft ( )
#, если уровень нечетный
# ставит в queue текущий узел
level_nodes . append ( curr )
# помещает данные текущего узла в stack
level_data . append ( curr . data )
#, если текущий узел является последним узлом уровня
# перевернуть уровень
level = not level
# поместил элементы, присутствующие в `level_data`, в их правильные
# Позиция # с использованием level_nodes
while level_nodes :
front = level_nodes . popleft ( ) # использует `popleft()` для queue
front . data = level_data . pop ( ) # использует `pop()` для stack
# ставит в queue левого дочернего элемента текущего узла
if curr . left :
q . append ( curr . left )
# ставит в queue правого потомка текущего узла
if curr . right :
q . append ( curr . right )
if __name__ == ‘__main__’ :
»’ Construct the following tree
8 9 10 11 12 13 14 15
root = Node ( 1 )
root . left = Node ( 2 )
root . right = Node ( 3 )
root . left . left = Node ( 4 )
root . left . right = Node ( 5 )
root . right . left = Node ( 6 )
root . right . right = Node ( 7 )
root . left . left . left = Node ( 8 )
root . left . left . right = Node ( 9 )
root . left . right . left = Node ( 10 )
root . left . right . right = Node ( 11 )
root . right . left . left = Node ( 12 )
root . right . left . right = Node ( 13 )
root . right . right . left = Node ( 14 )
root . right . right . right = Node ( 15 )
invertBinaryTree ( root )
levelOrderTraversal ( root )
результат:
1 3 2 4 5 6 7 15 14 13 12 11 10 9 8
Временная сложность приведенного выше решения равна O(n) , куда n это общее количество узлов в бинарном дереве. Программа требует O(n) дополнительное пространство для хранения узлов, присутствующих на нечетных уровнях двоичного дерева. Stack предпочтительнее списка для хранения узлов, поскольку это структура данных LIFO, и нам не нужно реверсировать ее перед присвоением значения узлам.
2. Использование обхода по порядку
Идея остается похожей на предыдущий подход, за исключением того, что здесь мы рекурсивно обходим дерево в мода, и узлы хранения представляют все нечетные уровни в stack и заменяют их позже, выполняя другой неупорядоченный обход. Этот подход демонстрируется ниже на C++, Java и Python: