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

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.