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);
  }
}