«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.