100. Same Tree

Задача

Даны корни двух бинарных деревьев p и q . Напишите функцию, которая проверяет, являются ли они одинаковыми или нет.

Два бинарных дерева считаются одинаковыми, если они структурно идентичны, и узлы имеют одинаковые значения.

Примеры

Пример 1

Input: p = [1,2,3], q = [1,2,3]
Output: true

Пример 2

Input: p = [1,2], q = [1,null,2]
Output: false

Пример 3

Input: p = [1,2,1], q = [1,1,2]
Output: false

Решение

Тестирование

// Определение узла дерева
function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val);
    this.left = (left === undefined ? null : left);
    this.right = (right === undefined ? null : right);
}
 
// Вспомогательная функция для создания дерева из массива (BFS)
function createTree(arr) {
    if (!arr || arr.length === 0) return null;
 
    let root = new TreeNode(arr[0]);
    let queue = [root];
    let i = 1;
 
    while (i < arr.length) {
        let current = queue.shift();
 
        // Левый ребенок
        if (i < arr.length && arr[i] !== null) {
            current.left = new TreeNode(arr[i]);
            queue.push(current.left);
        }
        i++;
 
        // Правый ребенок
        if (i < arr.length && arr[i] !== null) {
            current.right = new TreeNode(arr[i]);
            queue.push(current.right);
        }
        i++;
    }
 
    return root;
}
 
// --- Тестовые данные из примеров ---
 
// Example 1: p = [1,2,3], q = [1,2,3]
const p1 = createTree([1, 2, 3]);
const q1 = createTree([1, 2, 3]);
 
// Example 2: p = [1,2], q = [1,null,2]
const p2 = createTree([1, 2]);
const q2 = createTree([1, null, 2]);
 
// Example 3: p = [1,2,1], q = [1,1,2]
const p3 = createTree([1, 2, 1]);
const q3 = createTree([1, 1, 2]);
 
// Проверка (замени isSameTree на свою функцию)
// console.log(isSameTree(p1, q1)); // true
// console.log(isSameTree(p2, q2)); // false
// console.log(isSameTree(p3, q3)); // false

Решение 1 (Recursion)

// Временная сложность: O (N), где N — количество узлов в меньшем из деревьев (так как мы посещаем каждый узел один раз).
// Пространственная сложность: O (H), где H — высота дерева (из-за стека вызовов рекурсии). В худшем случае (вырожденное дерево-список) это O (N), в лучшем (сбалансированное) — O(logN).
 
var isSameTree = function(p, q) {
    if (!p && !q) return true;
    if (!p || !q) return false;
    return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

Решение 2 (Loop + Queue)

/**
 * Временная сложность: O(N)
 * Пространственная сложность: O(N) (в худшем случае храним нижний уровень дерева)
 */
var isSameTree = function(p, q) {
    // Используем один общий массив как очередь, храня пары узлов для сравнения
    const queue = [[p, q]];
 
    while (queue.length > 0) {
        // Достаем пару узлов
        const [node1, node2] = queue.shift();
 
        // 1. Оба узла null -> это нормально, идем дальше
        if (!node1 && !node2) continue;
 
        // 2. Один null, а другой нет ИЛИ значения разные -> деревья разные
        if (!node1 || !node2 || node1.val !== node2.val) return false;
 
        // 3. Если узлы одинаковые, добавляем их детей в очередь для проверки
        queue.push([node1.left, node2.left]);
        queue.push([node1.right, node2.right]);
    }
 
    return true;
};