题目描述

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

样例

输入: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。

输入: 

          1
         /  
        3    
       / \       
      5   3     

输出: 2
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。

输入: 

          1
         / \
        3   2 
       /        
      5      

输出: 2
解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。

输入: 

          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
输出: 8
解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。

算法1

联系到满二叉树给每个结点的标号，在层次遍历的时候同时记录每个点的index，求出每层宽度再取max即可

时间复杂度 $O(n)$

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
typedef unsigned int ui;
typedef pair<TreeNode*,ui> PTU;
class Solution {
public:
    int d = 0;
    void getans(TreeNode* root){
        queue<PTU>Q;
        Q.push({root,0});
        TreeNode* p = root;
        while(!Q.empty()){
            int l = 0,r = 0,len = Q.size();
            for(int i = 0;i < len;++i){
                if(i == 0) l = Q.front().second;
                if(i == len - 1)r = Q.front().second;
                p = Q.front().first;
                if(p->left){
                    Q.push({p->left,2*Q.front().second + 1});
                }
                if(p->right){
                    Q.push({p->right,2*Q.front().second + 2});
                }
                Q.pop();
            }
            d = max(d,r - l + 1);
        }
    }
    int widthOfBinaryTree(TreeNode* root) {
        getans(root);
        return d;
    }
};