Задача: 958. Check Completeness of a Binary Tree
Сложность: medium

Дан корень бинарного дерева, определите, является ли оно полным бинарным деревом.

В полном бинарном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. На последнем уровне h может быть от 1 до 2^h узлов включительно.

Пример:

Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

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

1⃣Если корень дерева равен null, верните true.

2⃣Инициализируйте переменную nullNodeFound как false для отслеживания того, встречался ли уже null-узел. Создайте очередь и поместите в неё корень дерева.

3⃣Пока очередь не пуста:
Извлеките первый элемент из очереди.
Если элемент равен null, установите nullNodeFound в true.
Если элемент не равен null, проверьте, встречался ли уже null-узел. Если nullNodeFound равен true, верните false. В противном случае добавьте в очередь левого и правого потомков текущего узла.

😎 Решение:

class Solution {
    /**
     * @param TreeNode $root
     * @return Boolean
     */
    function isCompleteTree($root) {
        if ($root === null) {
            return true;
        }

        $queue = [$root];
        $nullNodeFound = false;

        while (!empty($queue)) {
            $node = array_shift($queue);
            
            if ($node === null) {
                $nullNodeFound = true;
            } else {
                if ($nullNodeFound) {
                    return false;
                }
                $queue[] = $node->left;
                $queue[] = $node->right;
            }
        }
        return true;
    }
}

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