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);
В предыдущем методе мы создали следующую структуру:
Перевернув дерево слева направо, мы получим следующую структуру:
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.