Задача: 199. Binary Tree Right Side View
Сложность: medium

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

Пример:

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

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

1⃣Инициализируйте список правого обзора rightside. Инициализируйте две очереди: одну для текущего уровня и одну для следующего. Добавьте корень в очередь nextLevel.

2⃣Пока очередь nextLevel не пуста:
Инициализируйте текущий уровень: currLevel = nextLevel и очистите очередь следующего уровня nextLevel.
Пока очередь текущего уровня не пуста:
Извлеките узел из очереди текущего уровня.
Добавьте сначала левый, а затем правый дочерний узел в очередь nextLevel.
Теперь очередь currLevel пуста, и узел, который у нас есть, является последним и составляет часть правого обзора. Добавьте его в rightside.

3⃣Верните rightside.

😎 Решение:

class Solution {
    public function rightSideView($root) {
        if ($root === null) return [];

        $nextLevel = [$root];
        $rightside = [];

        while (!empty($nextLevel)) {
            $currLevel = $nextLevel;
            $nextLevel = [];

            foreach ($currLevel as $node) {
                if ($node->left !== null) $nextLevel[] = $node->left;
                if ($node->right !== null) $nextLevel[] = $node->right;
            }

            $rightside[] = end($currLevel)->val;
        }
        return $rightside;
    }
}

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