Условие. Нужно инвертировать двоичное дерево. Т.е. поменять местами все левые и правые вершины. Например:
Решение. Для решения будем использовать 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);
}
}
Top comments (0)