题意：


方法一：
bfs

思路：
        层次遍历。
        核心：为每个节点都赋值个id。（例：已知当前父节点的id,则左儿子为id*2,右儿子为id*2+1。）
        利用队列实现一层一层的遍历树，计算每一层的宽度=每一层的最大值id与最小值id的差值+1。
        并且维护每层的宽度值，即可得树的宽度值。
 



class Solution {
public:
    
    int widthOfBinaryTree(TreeNode* root) {
        if(root==nullptr)
            return 0;
        int res=0;//最大宽度
        queue<pair<TreeNode*,int>> q;//队列
        q.push({root,1});//根节点入队列
        while(!q.empty()){//队列非空
            int cnt=q.size();
            int ma=0,mi=INT_MAX;
            while(cnt--){//一层一层的遍历
                auto t=q.front();
                q.pop();
                TreeNode *p=t.first;
                int id=t.second;
                ma=max(ma,id);//维护id的最大值
                mi=min(mi,id);//维护id的最小值
                if(p->left){
                    q.push({p->left,id*2});//左儿子入队列
                }
                if(p->right){
                    q.push({p->right,id*2+1});//右儿子入队列
                }
            }
            res=max(res,ma-mi+1);//维护最大宽度
        }
        return res;
    }
};


时间复杂度：
空间复杂度：

方法二：
dfs

思路：
        dfs。
        核心：为每个节点都赋值个id。（例：已知当前父节点的id,则左儿子为id*2,右儿子为id*2+1。）
   
        初始化mi[ ]表示不同深度的id的最小值，ma[ ]表示不同深度的id的最大值；
        利用深度优先搜索遍历每个节点，维护不同深度的id最小值和id最大值。
        最后，计算不同深度的id最小值与最大值的差值，得到不同层的宽度，并维护宽度的最大值。

        
class Solution {
public:
    int mi[10005]={0};//mi[]表示不同深度的id的最小值
    int ma[10005]={0};//ma[]表示不同深度的id的最大值
    int maDepth=0;//最大深度
    int widthOfBinaryTree(TreeNode* root) {
        if(root==nullptr)
            return 0;
        memset(mi,0x3f,sizeof(mi));
        dfs(root,1,1);//递归
        int res=0;//最大宽度
        for(int i=1;i<=maDepth;i++){//维护树的最大宽度
//             cout << mi[i] << " " << ma[i] << " " << (ma[i]-mi[i]+1) << endl;
            res=max(res,ma[i]-mi[i]+1);
        }
        return res;
    }
    
    void dfs(TreeNode *root,int id,int dep){
        if(root==nullptr)
            return;
        maDepth=max(maDepth,dep);
        mi[dep]=min(mi[dep],id);//维护最小值
        ma[dep]=max(ma[dep],id);//维护最大值
        if(root->left){
            dfs(root->left,id*2,dep+1);//递归左儿子
        }
        if(root->right){
            dfs(root->right,id*2+1,dep+1);//递归右儿子
        }
    }
};

时间复杂度：
空间复杂度：