Для понимания подхода к решению обратитесь к статье здесь.

Вопрос. Для заданного двоичного дерева напишите функцию для получения максимальной ширины заданного дерева. Максимальная ширина дерева — это максимальная ширина среди всех уровней.

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

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

Пример 1:

Input: 
           1
         /   \
        3     2
       / \     \  
      5   3     9 
Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).

Пример 2:

Input: 
          1
         /  
        3    
       / \       
      5   3     
Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).

Пример 3:

Input: 
          1
         / \
        3   2 
       /        
      5      
Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).

Пример 4:

Input: 
          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).

Ограничения:

Данное бинарное дерево будет иметь от 1 до 3000 узлов.

Код С++ для вышеуказанной проблемы выглядит следующим образом:

int widthOfBinaryTree(TreeNode* root) {
        if(!root) return 0;
        queue<pair<TreeNode*, unsigned long long int>> Q;
        Q.push({root, 1}), Q.push({NULL, -1});
        unsigned long long int l=1, r=1, mx = 0;
        while(!Q.empty()){
            auto tmp = Q.front();
            Q.pop();
            TreeNode *var = tmp.first;
            unsigned long long int v = tmp.second;
            if(var==NULL ){
                if(!Q.empty()){
                    mx = max(mx, (r-l + 1));
                    l = Q.front().second;
                    Q.push({NULL,-1});
                }
                else{
                    mx = max(mx, (r-l + 1));
                    break;
                }
            }
            else{
                r = v;                
                if(var->left) Q.push({var->left,2*v});
                if(var->right) Q.push({var->right, 2*v+1});
            }
        }
    return mx;
}

Временная сложность: O(N)то же, что и BFS, в конце концов, мы просто проходим каждый уровень слева направо (BFS/ обход порядка уровней).

Удачного кодирования!!!