C++ STL中循环直接使用queue::size()为何会导致二叉树左视图代码输出错误
问题原因解答
核心问题出在队列长度的动态变化特性,以及BFS层序遍历的逻辑要求:
- 你实现左视图用到的是层序遍历(BFS),每轮
while循环的目标是完整处理当前层级的所有节点。进入while循环的瞬间,队列中存储的恰好是当前层级的全部节点,此时的q.size()就是当前层级的节点总数。 - 如果你直接把
q.size()写在for循环的判断条件里:每次循环判断条件时都会重新读取队列的实时长度,而你在循环体内会将当前节点的左右子节点push进队列,每push一次队列长度就会+1。这就会导致for循环不会在处理完当前层节点后停止,会把新入队的下一层节点也放在本轮循环处理,完全打乱了按层遍历的逻辑,自然无法正确识别每一层的第一个节点(左视图的输出就是每层第一个节点),最终输出错误。 - 你先把进入
while时的q.size()赋值给固定变量size,for循环的终止值就是固定的当前层节点数,循环只会刚好处理完当前层的所有节点,新push的下一层节点会留在队列里等下一轮while循环处理,逻辑完全正确,输出就符合预期。
举个简单的场景验证:
进入第一层处理逻辑时,队列中只有根节点,此时q.size()=1:
如果直接写i<q.size():
- i=0 满足条件,处理根节点,
pop后队列为空,随后push根节点的左右子节点,此时队列长度变为2 - i自增为1,判断
1<2满足条件,继续循环,此时本应该属于第二层的节点被提前放到第一层的循环里处理,i==0的左视图判断逻辑只会触发1次,输出自然错误。
内容的提问来源于stack exchange,提问作者Akarsh369
相关产品推荐
相关产品推荐

