Перейти к основному содержимому

Реверсирование двоичного дерева в Java

· 3 мин. чтения

1. Обзор

Реверсирование бинарного дерева — одна из задач, которую нам могут предложить решить во время технического собеседования .

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

2. Бинарное дерево

Двоичное дерево — это структура данных, в которой каждый элемент имеет не более двух дочерних элементов , называемых левым дочерним элементом и правым дочерним элементом. Верхний элемент дерева — это корневой узел, а дочерние — внутренние узлы .

Однако, если узел не имеет потомка, он называется листом.

Сказав это, давайте создадим наш объект, представляющий узел:

public class TreeNode {

private int value;
private TreeNode rightChild;
private TreeNode leftChild;

// Getters and setters

}

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

TreeNode leaf1 = new TreeNode(1);
TreeNode leaf2 = new TreeNode(3);
TreeNode leaf3 = new TreeNode(6);
TreeNode leaf4 = new TreeNode(9);

TreeNode nodeRight = new TreeNode(7, leaf3, leaf4);
TreeNode nodeLeft = new TreeNode(2, leaf1, leaf2);

TreeNode root = new TreeNode(4, nodeLeft, nodeRight);

В предыдущем методе мы создали следующую структуру:

./9308ef74d1c94dcde84afca66cbb8676.png

Перевернув дерево слева направо, мы получим следующую структуру:

./2a5072cc63956692cc439c25d8733dbf.png

3. Обращение бинарного дерева

3.1. Рекурсивный метод

В первом примере мы будем использовать рекурсию для реверсирования дерева .

Прежде всего, мы вызовем наш метод, используя корень дерева, затем применим его к левому и правому дочерним элементам соответственно , пока не достигнем листьев дерева:

public void reverseRecursive(TreeNode treeNode) {
if(treeNode == null) {
return;
}

TreeNode temp = treeNode.getLeftChild();
treeNode.setLeftChild(treeNode.getRightChild());
treeNode.setRightChild(temp);

reverseRecursive(treeNode.getLeftChild());
reverseRecursive(treeNode.getRightChild());
}

3.2. Итерационный метод

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

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

Мы продолжаем добавлять и удалять из LinkedList , пока не достигнем листьев дерева:

public void reverseIterative(TreeNode treeNode) {
List<TreeNode> queue = new LinkedList<>();

if(treeNode != null) {
queue.add(treeNode);
}

while(!queue.isEmpty()) {
TreeNode node = queue.poll();
if(node.getLeftChild() != null){
queue.add(node.getLeftChild());
}
if(node.getRightChild() != null){
queue.add(node.getRightChild());
}

TreeNode temp = node.getLeftChild();
node.setLeftChild(node.getRightChild());
node.setRightChild(temp);
}
}

4. Вывод

В этой быстрой статье мы рассмотрели два способа обращения двоичного дерева. Мы начали с использования рекурсивного метода, чтобы обратить его. Затем мы использовали итеративный способ для достижения того же результата.

Полный исходный код этих примеров и модульных тестов можно найти на Github.