404. Sum of Left Leaves

Задача

Дан корень (root) бинарного дерева, верните сумму всех левых листьев.

Лист (leaf) — это узел, не имеющий детей. Левый лист (left leaf) — это лист, который является левым ребёнком другого узла.

Примеры

Пример 1

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

Пояснение

В дереве два левых листа со значениями 9 и 15.

Пример 2

Input: root = [1]
Output: 0

Решение

Решение

/**
 * Временная сложность: O(N) — мы посещаем каждый узел дерева ровно один раз.
 * Пространственная сложность: O(N) — в худшем случае (вырожденное дерево типа "линия") стек будет хранить N узлов. В сбалансированном дереве — O(log N).
 */
var sumOfLeftLeaves = function(root) {
    if (!root) return 0; // Важная проверка для пустого дерева
 
    let stack = [root];
    let sum = 0;
 
    while (stack.length) {
        const node = stack.pop();
 
        // Проверяем, является ли левый ребенок ЛИСТОМ
        // 1. node.left существует
        // 2. у node.left нет левого ребенка
        // 3. у node.left нет правого ребенка
        if (node.left && !node.left.left && !node.left.right) {
            sum += node.left.val;
        }
 
        if (node.left) stack.push(node.left);
        if (node.right) stack.push(node.right);
    }
 
    return sum;
};

Решение 2 (DFS + Recursion)

/**
 * Временная сложность: O(N)
 * Пространственная сложность: O(N) (стек вызовов)
 */
var sumOfLeftLeaves = function(root) {
 
    // Вспомогательная функция с параметром isLeft
    function traverse(node, isLeft) {
        if (!node) return 0;
 
        // Если это лист и он левый - возвращаем его значение
        if (!node.left && !node.right && isLeft) {
            return node.val;
        }
 
        // Иначе суммируем результаты детей
        // true для левого ребенка, false для правого
        return traverse(node.left, true) + traverse(node.right, false);
    }
 
    return traverse(root, false);
};

Решение 3 (BFS + Queue)

/**
 * Временная сложность: O(N)
 * Пространственная сложность: O(W) - ширина дерева (макс. количество узлов на уровне)
 */
var sumOfLeftLeaves = function(root) {
    if (!root) return 0;
 
    const queue = [root];
    let sum = 0;
 
    while (queue.length) {
        const node = queue.shift();
 
        if (node.left && !node.left.left && !node.left.right) {
            sum += node.left.val;
        }
 
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
 
    return sum;
};