二叉树层序遍历实现是否正确？大输入规模下会有问题吗？

我写的二叉树层序遍历C++代码能输出正确结果，但想了解这种实现方法在处理大规模输入时是否会出现问题，刚接触数据结构，代码如下：

#include <bits/stdc++.h> 
using namespace std;

//LEVEL ORDER TRAVERSAL

class node{
 private: int data;
 public : node* left=NULL;node *right=NULL;
 node(int dat){
     data=dat;
 } 
 int getVal(){
     return data;
 }
};

void level_order(node *a,queue<node*> q){
  if(a->left!=NULL){
    q.push(a->left);
  }
  if(a->right!=NULL){
    q.push(a->right);
  }
  cout<<a->getVal()<<",";
  q.pop();
  if(!q.empty()){
  level_order(q.front(),q);}
}

int main(){
    node* root=new node(1);
    root->left=new node(2);
    root->right=new node(3);
    root->left->left=new node(4);
    root->left->right=new node(5);
    root->left->right->left=new node(6);
    root->right->left=new node(7);
    root->right->right=new node(8);
    root->right->right->left=new node(9);
    root->right->right->right=new node(10);
    queue<node*> a;
    a.push(root);
    level_order(root,a);
    return 0;
}

你的代码在小规模测试中能正常运行，但处理大规模二叉树时会出现严重问题，核心原因是队列按值传递+递归实现的组合，具体问题如下：

• 内存开销爆炸：每次递归调用level_order时，都会复制整个队列。当二叉树有十万甚至百万级节点时，无数个队列副本会占用巨量内存，很快就会导致内存不足，程序崩溃。
• 递归栈溢出：递归深度等于二叉树的层数。如果是链式结构的二叉树（比如每个节点只有左孩子），层数等于节点数，一旦节点数超过系统默认的递归栈大小（通常是几MB，对应几千到几万层），就会触发栈溢出错误。
• 运行效率极低：队列复制的时间复杂度是O(k)（k为当前队列长度），整个遍历的时间复杂度会从正常的O(n)退化到O(n²)，大规模数据下运行速度会慢到无法接受。

正确的迭代式实现 #

层序遍历的标准实现是用迭代+单个队列，避免递归和队列复制，适合处理大规模数据：

#include <bits/stdc++.h>
using namespace std;

class node{
private: int data;
public: node* left=NULL; node *right=NULL;
node(int dat){
    data=dat;
}
int getVal(){
    return data;
}
};

void level_order(node* root){
    if(!root) return; // 空树直接返回
    queue<node*> q;
    q.push(root);
    while(!q.empty()){
        node* curr = q.front();
        q.pop();
        cout << curr->getVal() << ",";
        // 先左后右加入队列
        if(curr->left) q.push(curr->left);
        if(curr->right) q.push(curr->right);
    }
}

int main(){
    node* root=new node(1);
    root->left=new node(2);
    root->right=new node(3);
    root->left->left=new node(4);
    root->left->right=new node(5);
    root->left->right->left=new node(6);
    root->right->left=new node(7);
    root->right->right=new node(8);
    root->right->right->left=new node(9);
    root->right->right->right=new node(10);
    level_order(root);
    return 0;
}

这个实现的优势：

• 只用一个队列，内存开销稳定在O(n)（队列最多存储一层的节点数，最坏情况是完全二叉树的最后一层，约n/2个节点）。
• 无递归调用，不会出现栈溢出问题。
• 时间复杂度是O(n)，每个节点入队和出队各一次，效率最高。

内容的提问来源于stack exchange，提问作者Kshitij_Jha_7