101. Symmetric Tree

Задача

Дан корень бинарного дерева. Проверьте, симметрично ли оно относительно центра.

Примеры

Пример 1

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

Пример 2

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

Решение

Решение

/**
 * Временная сложность: O(N) — мы посещаем каждый узел ровно один раз.
 * Пространственная сложность: O(H) — в худшем случае глубина рекурсии равна высоте дерева (для сбалансированного O(log N), для линии O(N)).
 */
var isSymmetric = function(root) {
    if (!root) return true;
 
    function isMirror(node1, node2) {
        // 1. Если оба узла пустые — они зеркальны (базовый случай)
        if (!node1 && !node2) return true;
 
        // 2. Если один пустой, а другой нет — не зеркальны
        if (!node1 || !node2) return false;
 
        // 3. Значения должны совпадать
        if (node1.val !== node2.val) return false;
 
        // 4. Рекурсия:
        // Левый ребенок первого должен быть зеркален правому ребенка второго
        // И правый ребенок первого — левому ребенка второго
        return isMirror(node1.left, node2.right) &&
            isMirror(node1.right, node2.left);
    }
 
    return isMirror(root.left, root.right);
};

Решение 2 (Stack)

var isSymmetric = function(root) {
    if (!root) return true;
 
    // Используем массив как очередь
    const queue = [root.left, root.right];
 
    while (queue.length > 0) {
        // Достаем два элемента из начала
        const node1 = queue.shift();
        const node2 = queue.shift();
 
        // 1. Если оба узла пустые — они зеркальны (базовый случай)
        if (!node1 && !node2) continue;
 
        // 2. Если один пустой, а другой нет — не зеркальны
        if (!node1 || !node2) return false;
 
        // 3. Значения должны совпадать
        if (node1.val !== node2.val) return false;
 
        // 3. Кладем детей в очередь парами (Зеркально!)
        queue.push(node1.left, node2.right); // Внешние
        queue.push(node1.right, node2.left); // Внутренние
    }
 
    return true;
};