Задача: 662. Maximum Width of Binary Tree
Сложность: medium

Дан корень бинарного дерева, верните максимальную ширину данного дерева.

Максимальная ширина дерева - это максимальная ширина среди всех уровней.

Ширина одного уровня определяется как расстояние между конечными узлами (самыми левыми и самыми правыми ненулевыми узлами), где нулевые узлы между конечными узлами, которые присутствовали бы в полном бинарном дереве, продолжающемся до этого уровня, также учитываются при вычислении длины.

Гарантируется, что ответ будет в диапазоне 32-битного знакового целого числа.

Пример:

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).

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

1⃣Инициализация:
Создайте очередь для хранения узлов и их позиций на уровне.
Начните с корневого узла и его позиции 0.

2⃣Обработка каждого уровня:
Для каждого уровня дерева получите его узлы и их позиции.
Вычислите ширину уровня как разницу между максимальной и минимальной позициями плюс один.

3⃣Обновление максимальной ширины:
Обновите максимальную ширину, если текущая ширина уровня больше.

😎 Решение:

class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    function widthOfBinaryTree($root) {
        if ($root === null) return 0;
        
        $maxWidth = 0;
        $queue = [[$root, 0]];

        while (!empty($queue)) {
            $levelSize = count($queue);
            $firstPos = $queue[0][1];
            for ($i = 0; $i < $levelSize; $i++) {
                list($node, $pos) = array_shift($queue);
                if ($node->left !== null) $queue[] = [$node->left, 2 * $pos];
                if ($node->right !== null) $queue[] = [$node->right, 2 * $pos + 1];
            }
            $lastPos = !empty($queue) ? end($queue)[1] : $firstPos;
            $maxWidth = max($maxWidth, $lastPos - $firstPos + 1);
        }

        return $maxWidth;
    }
}

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