PrepBro
← Назад к вопросам

Инвертирование бинарного дерева

1.0 Junior🔥 81 комментариев
#Другое#Основы Java

Условие

Инвертируйте бинарное дерево (отразите его зеркально).

Примеры

Вход:

     4
   /   \\
  2     7
 / \\   / \\
1   3 6   9

Выход:

     4
   /   \\
  7     2
 / \\   / \\
9   6 3   1

Требования

  • Реализуйте рекурсивное решение
  • Реализуйте итеративное решение с очередью
  • Временная сложность O(n)
  • Пространственная сложность O(h) для рекурсии, O(n) для итеративного

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Инвертирование бинарного дерева

Эта классическая задача на обход дерева демонстрирует рекурсивное и итеративное решение. Инвертирование означает зеркальное отражение дерева — левое поддерево становится правым и наоборот.

Определение узла дерева

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}
    
    TreeNode(int val) {
        this.val = val;
    }
    
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Решение 1: Рекурсивное (простое и элегантное)

Основная идея: для каждого узла поменяем его левое и правое поддеревья местами, затем рекурсивно инвертируем каждое поддерево.

class Solution {
    public TreeNode invertTree(TreeNode root) {
        // Базовый случай: если узла нет
        if (root == null) {
            return null;
        }
        
        // Меняем левое и правое поддеревья
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        // Рекурсивно инвертируем левое поддерево
        invertTree(root.left);
        
        // Рекурсивно инвертируем правое поддерево
        invertTree(root.right);
        
        return root;  // Возвращаем инвертированное дерево
    }
}

Более компактная версия:

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        
        // Меняем местами и сразу вызываем рекурсию
        TreeNode temp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(temp);
        
        return root;
    }
}

Анализ:

  • Временная сложность: O(n) — посещаем каждый узел один раз
  • Пространственная сложность: O(h) — глубина рекурсии, где h — высота дерева
    • В сбалансированном дереве: O(log n)
    • В худшем случае (линейное дерево): O(n)

Решение 2: Итеративное с очередью (BFS)

Используем очередь для обхода дерева уровень за уровнем:

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);  // Начинаем с корня
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();  // Берём узел из очереди
            
            // Меняем левое и правое поддеревья
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            
            // Добавляем дочерние узлы в очередь
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        
        return root;
    }
}

Анализ:

  • Временная сложность: O(n) — посещаем каждый узел один раз
  • Пространственная сложность: O(w) — ширина дерева (макс. узлов на уровне)
    • В сбалансированном дереве: O(n/2) = O(n)
    • В худшем случае: O(n)

Решение 3: Итеративное со стеком (DFS)

Используем стек для обхода глубину-в-первую:

import java.util.Stack;

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);  // Начинаем с корня
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();  // Берём узел из стека
            
            // Меняем левое и правое поддеревья
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            
            // Добавляем дочерние узлы в стек
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        
        return root;
    }
}

Анализ:

  • Временная сложность: O(n)
  • Пространственная сложность: O(h) в среднем, O(n) в худшем случае

Пошаговое объяснение

Для дерева:

     4
   /   \\
  2     7
 / \\   / \\
1   3 6   9

Рекурсивное решение:

Шаг 1: invertTree(4)
  - Меняем: left=7, right=2
  - Дерево: 4 (7 слева, 2 справа)
  
Шаг 2: invertTree(7)  (раньше был справа)
  - Меняем: left=9, right=6
  - Дерево: 7 (9 слева, 6 справа)
  
Шаг 3: invertTree(9)
  - Базовый случай (листовой узел)
  
Шаг 4: invertTree(6)
  - Базовый случай
  
Шаг 5: invertTree(2)  (раньше был слева)
  - Меняем: left=3, right=1
  - Дерево: 2 (3 слева, 1 справа)
  
Шаг 6: invertTree(3)
  - Базовый случай
  
Шаг 7: invertTree(1)
  - Базовый случай

Результат:
     4
   /   \\
  7     2
 / \\   / \\
9   6 3   1

Полный тестовый код

import java.util.Queue;
import java.util.LinkedList;

public class TreeInversion {
    public static void main(String[] args) {
        // Создаём исходное дерево
        //      4
        //    /   \\
        //   2     7
        //  / \\   / \\
        // 1   3 6   9
        
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(9);
        
        System.out.println("Исходное дерево (в порядке обхода):");
        inorder(root);  // 1 2 3 4 6 7 9
        System.out.println();
        
        // Инвертируем дерево (рекурсивно)
        root = invertTree(root);
        
        System.out.println("Инвертированное дерево:");
        inorder(root);  // 9 7 6 4 3 2 1
        System.out.println();
    }
    
    public static TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        
        // Меняем левое и правое поддеревья
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        // Рекурсивно инвертируем
        invertTree(root.left);
        invertTree(root.right);
        
        return root;
    }
    
    // Вспомогательный метод для вывода дерева (in-order)
    public static void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
}

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Вывод:

Исходное дерево (в порядке обхода):
1 2 3 4 6 7 9

Инвертированное дерево:
9 7 6 4 3 2 1

Сравнение подходов

ПодходВремяПамятьПлюсыМинусы
РекурсияO(n)O(h)Элегантно, простоStack overflow на глубоких деревьях
BFS (очередь)O(n)O(w)Визуально понятноБольше памяти для широких деревьев
DFS (стек)O(n)O(h)Контроль порядкаМенее интуитивно

Оптимизация памяти

Используйте рекурсию для экономии памяти:

// Лучший выбор для большинства случаев
public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode temp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(temp);
    return root;
}

Key Points

  1. Инвертирование — простой swap левого и правого
  2. Рекурсия — самое элегантное решение
  3. Итеративность — избегает переполнения стека
  4. BFS vs DFS — выбирайте в зависимости от формы дерева
  5. O(n) время — обязательно для всех узлов
Инвертирование бинарного дерева | PrepBro