求二叉树宽度，递归错误

Question

求二叉树宽度

无法递归

void Treelevelmax(bitree T,LQueue qa, int &sum)//求二叉树宽度
{
    LQueue z;
    InitQueue(z);
    bitree p;
    int temp=0;
    while (!QueueEmpty(qa)){        
        DeQueue(qa,p);
        if(p->left!=NULL)EnQueue(z,p->left);temp++;
        if(p->right!=NULL)EnQueue(z,p->right);temp++;
    }
        while(!QueueEmpty(z)){
            DeQueue(z,p);
        char a=p->data;
            printf("%c",a);}
     sum=sum>=temp?sum:temp;
    if(!QueueEmpty(z)){
        qa=z;
        Treelevelmax(T,qa,sum);}
        else return ;
    
}    

用代码块功能插入代码，请勿粘贴截图。 不用代码块回答率下降 50%

采用双对列方法，qa和z ,qa取根节点，z取根节点的左右节点并累计求和。以此类推，求出每一层的节点和，并比较大小，取最大值

我的解答思路和尝试过的方法

我想要达到的结果，如果你需要快速回答，请尝试 “付费悬赏”

Answer 1

这段代码有一个问题，在第一个 while 中，会对左右子节点进行多次重复累计，会导致求得不是二叉树的真实宽度。

下面是一种求二叉树宽度的方法，使用层次遍历，并记录每一层的节点数，取最大值即为二叉树的宽度。

int maxWidth(TreeNode *root) {
    if(!root) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int res = 0;
    while(!q.empty()) {
        int size = q.size();
        res = max(res, size);
        while(size--) {
            auto t = q.front(); q.pop();
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
    }
    return res;
}

该代码中，使用了STL库中的queue，每次从队列中出队当前节点，并将当前节点的左右子节点加入队列中，累计节点数时只需在记录当前层节点数时记录队列长度即可。

这样就可以得到二叉树的真实宽度了。