226. Invert Binary Tree

Задача

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

Примеры

Пример 1

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Пример 2

Input: root = [2,1,3]
Output: [2,3,1]

Пример 3

Input: root = []
Output: []

Решение

Решение

// Time:  O(n)  — каждый узел обрабатывается 1 раз
// Space: O(h)  — стек рекурсии, worst-case O(n)
var invertTree = function(root) {
    if (!root) return null;
    [root.left, root.right] = [root.right, root.left];
    invertTree(root.left);
    invertTree(root.right);
    return root;
};

Решение 2 (DFS Stack)

// Time: O(n), Space: O(h) average / O(n) worst-case (стек)
var invertTree = function(root) {
    if (!root) return null;
    const stack = [root];
 
    while (stack.length) {
        const node = stack.pop();
        [node.left, node.right] = [node.right, node.left];
        if (node.left) stack.push(node.left);
        if (node.right) stack.push(node.right);
    }
    return root;
};

Решение 3 (BFS)

// Time: O(n), Space: O(n) worst-case (очередь)
var invertTree = function(root) {
    if (!root) return null;
    const q = [root];
    let i = 0;
 
    while (i < q.length) {
        const node = q[i++];
        [node.left, node.right] = [node.right, node.left];
        if (node.left) q.push(node.left);
        if (node.right) q.push(node.right);
    }
    return root;
};