二叉树(微博搜索)-20230917-1

本条微博地址 计算机考研刘财政
考研 #数据结构# #玩转数据结构# #玩转计算机组成原理# #考研# #计算机考研#
算法冲刺 每日一题 必背上分 【第三十二天： 二叉树的应用】
3、求二叉树的宽度
所谓二叉树的宽度是指：二叉树各层节点个数的最大值。
算法思想：要求的是对于特定某一层的节点的个数，因此我们需要从头结点开始，记录每一层的个数，对于当前层的每一个节点，在弹出自身之后把其左右子树压入deque，当把当前层全部弹出队列之后，在队列中剩下的就是下一层的节点。然后比较队列的size和之前得到的maxWidth，取最大值即为队列的宽度。最终队列为空，得到的maxWidth就是二叉树的宽度。
int treeWidth(Bitree *root){
if(!root){ return 0; }
int width = 0;
int maxWidth = 0;
queue<Bitree *> Q;
Bitree *p = nullptr;
Q.push(root);
while(!Q.empty()){
width = Q.size();
if(maxWidth < width){
maxWidth = width;
}
for(int i=0; i<width; i++){
p = Q.front();
Q.pop();
if(p->left){
Q.push(p->left);
}
if(p->right){
Q.push(p->right);
}
}
}
return maxWidth;
}