Invert Binary Tree

Условие. Нужно инвертировать двоичное дерево. Т.е. поменять местами все левые и правые вершины. Например:

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

Двоичное дерево — дерево, в котором каждая вершина имеет не более двух дочерних вершин (их называют левым и правым ребенком).

Class BinaryTree:

    class BinaryTree {
      public int value;
      public BinaryTree left;
      public BinaryTree right;

      public BinaryTree(int value) {
        this.value = value;
      }
    }

Для двоичного дерева алгоритм DFS упростится до:

    public static void dfs(BinaryTree tree) {
      if (tree == null) {
        return;
      }
      visit(tree);
      dfs(tree.left);
      dfs(tree.right);
    }

Для деревьев нам не нужно помечать вершины посещенными, потому что в дереве нет циклов по определению. Мы будем идти от родительских вершин к дочерним.

Такой алгоритм обхода двоичного дерева называется pre-order traversal: Tree Traversal.

Мы вначале посещаем вершину, а потом вызываем рекурсивно для левого и правого ребенка.

Есть еще вариации обхода двоичного дерева, которые называются соответственно in-order (вначале посещаем левого ребенка, потом вершину, потом правого ребенка):

    public static void dfs(BinaryTree tree) {
      if (tree == null) {
        return;
      }
      dfs(tree.left);
      visit(tree);
      dfs(tree.right);
    }

И post-order (вначале посещаем левого и правого ребенка, а потом уже саму вершину):

    public static void dfs(BinaryTree tree) {
      if (tree == null) {
        return;
      }
      dfs(tree.left);
      dfs(tree.right);
      visit(tree);
    }

Вернемся к задаче. Будем идти по дереву и для каждой вершины менять местами левого и правого ребенка. И рекурсивно вызывать алгоритм для левой и правой вершины. Т.е. будем использовать pre-order обход двоичного дерева. Базовым условием выхода из функции является отсутствие вершины (достигли листовой вершины дерева tree == null).

Реализация:

    class Program {
      public static void invertBinaryTree(BinaryTree tree) {
        if (tree == null) {
          return;
        }
        //Меняем местами левого и правого ребенка
        BinaryTree tmp = tree.left;
        tree.left = tree.right;
        tree.right = tmp;
        //Рекурсивно вызываем функцию для левого и правого ребенка
        invertBinaryTree(tree.left);
        invertBinaryTree(tree.right);
      }
    }