104. Maximum Depth of Binary Tree

Задача

Дан корень бинарного дерева. Верните его максимальную глубину.

Примеры

Пример 1

Input: root = [3,9,20,null,null,15,7]
Output: 3

Пример 2

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

Решение

Решение

/**
 * Временная сложность: O(N)
 * Пространственная сложность: O(H) (высота дерева)
 */
var maxDepth = function(root) {
    if (!root) return 0;
 
    // Глубина = 1 (сам узел) + макс. глубина потомков
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};

Решение 2 (BFS)

/**
 * Временная сложность: O(N)
 * Пространственная сложность: O(W) (ширина дерева)
 */
var maxDepth = function(root) {
    if (!root) return 0;
 
    const queue = [root];
    let depth = 0;
 
    while (queue.length > 0) {
        depth++; // Начали новый уровень
        const levelSize = queue.length; // Фиксируем количество узлов на ЭТОМ уровне
 
        // Обрабатываем все узлы текущего уровня
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
 
    return depth;
};

Решение 3 (DFS)

var maxDepth = function(root) {
    if (!root) return 0;
 
    const stack = [
        [root, 1]
    ];
    let maxD = 0;
 
    while (stack.length) {
        const [node, currentDepth] = stack.pop();
 
        if (node) {
            maxD = Math.max(maxD, currentDepth);
            stack.push([node.left, currentDepth + 1]);
            stack.push([node.right, currentDepth + 1]);
        }
    }
 
    return maxD;
};