111. Minimum Depth of Binary Tree

Задача

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

Примеры

Пример 1

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

Пример 2

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

Решение

Решение

// Time: O(n), Space: O(h) (worst-case O(n))
var minDepth = function(root) {
    if (!root) return 0;
 
    if (!root.left && !root.right) return 1;
    if (!root.left && root.right) return 1 + minDepth(root.right);
    if (root.left && !root.right) return 1 + minDepth(root.left);
 
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
};

Решение 2 (BFS)

// Time: O(n), Space: O(n)
var minDepthBFS = function(root) {
    if (!root) return 0;
 
    const q = [root];
    let head = 0;
    let depth = 1;
 
    while (head < q.length) {
        const levelSize = q.length - head;
 
        for (let i = 0; i < levelSize; i++) {
            const node = q[head++];
 
            if (!node.left && !node.right) return depth; // первый найденный лист на минимальной глубине
            if (node.left) q.push(node.left);
            if (node.right) q.push(node.right);
        }
 
        depth++;
    }
 
    return depth;
};