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

😎 Решение:

using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public int WidthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        
        int maxWidth = 0;
        Queue<(TreeNode node, int pos)> queue = new Queue<(TreeNode, int)>();
        queue.Enqueue((root, 0));
        
        while (queue.Count > 0) {
            int levelSize = queue.Count;
            int firstPos = queue.Peek().pos;
            for (int i = 0; i < levelSize; i++) {
                var (node, pos) = queue.Dequeue();
                if (node.left != null) queue.Enqueue((node.left, 2 * pos));
                if (node.right != null) queue.Enqueue((node.right, 2 * pos + 1));
            }
            maxWidth = Math.Max(maxWidth, queue.Peek().pos - firstPos + 1);
        }
        
        return maxWidth;
    }
}

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