Задача: 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⃣Обновление максимальной ширины:
Обновите максимальную ширину, если текущая ширина уровня больше.

😎 Решение:

var widthOfBinaryTree = function(root) {
    if (!root) return 0;

    let maxWidth = 0;
    const queue = [{ node: root, pos: 0 }];

    while (queue.length > 0) {
        const levelSize = queue.length;
        const firstPos = queue[0].pos;
        for (let i = 0; i < levelSize; i++) {
            const { node, pos } = queue.shift();
            if (node.left) queue.push({ node: node.left, pos: 2 * pos });
            if (node.right) queue.push({ node: node.right, pos: 2 * pos + 1 });
        }
        const lastPos = queue[queue.length - 1]?.pos || firstPos;
        maxWidth = Math.max(maxWidth, lastPos - firstPos + 1);
    }

    return maxWidth;
};

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