Задача: 1302. Deepest Leaves Sum
Сложность: medium

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

Пример:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

👨‍💻 Алгоритм:

1⃣Поместите корень в стек.

2⃣Пока стек не пуст. Извлеките узел из стека и обновите текущее число. Если узел является листом, обновите сумму самых глубоких листьев deepest_sum. Поместите правый и левый дочерние узлы в стек.

3⃣Верните deepest_sum.

😎 Решение:

class Solution {
    function deepestLeavesSum($root) {
        $deepestSum = 0;
        $depth = 0;
        $stack = [[$root, 0]];

        while (!empty($stack)) {
            list($node, $currDepth) = array_pop($stack);

            if ($node->left === null && $node->right === null) {
                if ($depth < $currDepth) {
                    $deepestSum = $node->val;
                    $depth = $currDepth;
                } elseif ($depth == $currDepth) {
                    $deepestSum += $node->val;
                }
            } else {
                if ($node->right !== null) {
                    $stack[] = [$node->right, $currDepth + 1];
                }
                if ($node->left !== null) {
                    $stack[] = [$node->left, $currDepth + 1];
                }
            }
        }
        return $deepestSum;
    }
}

Ставь 👍 и забирай 📚 Базу знаний