提到二叉树的层序遍历绝大多数人第一反应是“开一个队列根节点入队然后循环出队、打印、再入队左右孩子”。教科书上这一套确实干净但有个小细节经常被一笔带过那个“队列”到底用什么实现默认答案通常是数组——分配一块连续内存维护头尾下标。可一旦遇到禁止用数组、禁止用递归的约束比如嵌入式裸机环境、底层库缺失或者纯粹想验证自己对指针和链表抽象的理解教科书方案就会直接失效。“使用链表实现的层序遍历 - 不使用数组和递归”这个题目我最近拿它做了一个完整落地项目。拆解下来会发现它其实不是“换一种姿势写同一段代码”而是把“队列”这个抽象从容器底层重新实现了一遍同时逼着你把递归思维切换成迭代思维。这篇文章就把我当时的完整思路、代码实现、踩坑记录都整理出来给同样被这个题目卡住的人一个可以直接抄作业的版本。1. 项目背景与核心问题拆解1.1 传统层序遍历的默认答案为什么是“数组队列”我见过太多教材写层序遍历时直接假定“队列”是一个已经存在的东西。用 C 语言写的时候最常见的做法是开一个足够大的数组头指针和尾指针各自往后移动int queue[MAX_N]; int head 0, tail 0;出队就是queue[head]入队就是queue[tail] value。这种写法在刷题软件里不会有任何问题因为测试用例的规模是预先定好的数组开大一点就完了。但真实项目里“开一个足够大的数组”这个前提本身就是隐患。你根本不知道树的最大宽度是多少一颗完全二叉树最后一层可能有几万个节点一颗退化链表树队列里任何时候都只有一个节点。用固定数组要么白白浪费一大块内存要么在最坏情况下直接溢出不给你任何容错机会。哪怕你改用动态扩容的数组方案本质上还是“连续内存 下标访问”那一套底层逻辑并没有变。这个项目选择链表实现队列最直接的理由就在这里队列的长度不需要预先知道入队一个节点就动态创建一个队列节点出队一个节点就释放一个队列节点内存占用和树的当前宽度严格成正比。不浪费也不溢出。另外还有一层现实原因在很多嵌入式或教学场景里标准库容器是不可用或者不被允许的。你不能指望环境里自带std::queue或者封装好的队列类型唯一能确定存在的就是malloc和指针。用链表实现队列是这套环境里最可靠、最可移植的方案。1.2 递归做层序遍历的三个真实困境“不用递归”这条约束乍看有点奇怪因为二叉树和递归绑定得太深了。但递归天然是深度优先的工具它靠系统调用栈保存路径信息而层序遍历是按宽度推进的两者本质上错位。最简单的递归式层序遍历是拿到一棵树之后先求出树的高度 H然后一层一层调用函数往下打印void printGivenLevel(TreeNode *root, int level) { if (root NULL) return; if (level 1) { printf(%d , root-data); return; } printGivenLevel(root-left, level - 1); printGivenLevel(root-right, level - 1); }每组 for 循环从第 0 层遍历到第 H 层每一层都要把整棵树重新走一遍。平衡二叉树的高度是 O(log n)总复杂度勉强能接受但一旦遇到退化树高度变成 O(n)每一层都从头递归一遍整体直接退化成 O(n²)。这个性能在几千层的时候就能肉眼可见地卡顿更不用说百万级节点了。更隐蔽的坑是系统栈深度。递归层序遍历时递归深度等于二叉树高度。普通开发机的函数栈空间通常只有几兆深度的二叉树递归到几万层就会栈溢出程序直接崩溃。这种崩溃还特别难排查因为它不是显式的错误信息而是一个措手不及的 segmentation fault。还有一种稍微聪明点的递归写法递归 DFS 的过程中把当前节点按照“所在层级”记录到一个结果容器里最后再按层输出。这种做法时间上是 O(n)但它至少依赖两样东西一个可动态增长的数组/向量容器以及递归调用栈本身。前者在“禁止数组”的约束下直接出局后者在深树场景下仍然有爆栈风险。所以“不用递归”不是题目故意刁难而是把层序遍历真正放回迭代思路的必由之路。1.3 链表方案的核心思路FIFO 语义不变存储介质更换想通之后你会发现这个题目的核心其实就一句话层序遍历的本质是广度优先搜索BFSBFS 的本质是先入先出FIFOFIFO 的天然物理载体就是队列。你只需要把队列的底层存储从数组换成链表其余逻辑保持不变。所以整个项目的设计思路可以拆成三条线树的遍历顺序完全由 BFS 算法决定与队列用数组还是链表无关。队列只负责“按顺序暂存待处理的树节点”它存的是树节点的指针不是树的拷贝。所有处理都发生在 while 循环里整个过程没有任何函数递归调用。换句话说这不是一个全新的遍历算法而是一个把“辅助数据结构”从内到外重新实现的项目。理解到这一层后面写代码就有了明确的方向先把链表队列封装好再套层序遍历框架问题自然解开。2. 数据结构设计与底层原理解析2.1 两套链表各司其职互不干扰很多人第一次写这个题目时容易走进一个误区试图把树的 left/right 指针改造成队列指针实现“复用节点”的效果。这个思路在特定面试题里确实存在比如完美二叉树的 next 指针连接问题但在这个项目里只会把事情搞复杂因为你一旦动了 left/right树的结构就被破坏了遍历结束后还要想办法恢复完全是自找麻烦。正确的做法是定义两套完全独立的结构体各管各的一亩三分地。树的节点只管树本身typedef struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; } TreeNode;队列的节点只管保存树节点的指针以及指向下一个队列节点的指针typedef struct QueueNode { TreeNode *tree; struct QueueNode *next; } QueueNode;这里一定要想清楚一件事队列节点里保存的是TreeNode *不是 TreeNode 本体。这意味着队列的入队出队操作只涉及指针的搬运完全不会复制树的数据。哪怕树有几十万个节点队列里任意时刻也只保存“当前层的节点指针”内存消耗被严格限制在当前层的宽度上。很多写着写着就乱了套的人问题多半出在搞混了这两套结构在队列入队的时候去改树节点的 left/right或者直接拿 TreeNode 冒充 QueueNode 用。记住这条原则就不会乱树节点属于树队列节点属于队列两者的关系是“队列节点引用树节点”仅此而已。2.2 队首队尾指针的边界处理是真正的考点链表队列本身是一个单向链表但和普通链表不同的是它必须同时维护两个指针front 指向链表头部出队时从这里取。rear 指向链表尾部入队时从这里插。入队的逻辑是标准的尾部插入但空队列是特例如果队列为空front 和 rear 都必须指向新节点如果队列不为空只需要把新节点挂到 rear 后面然后更新 rear。出队的逻辑是标准头部删除但同样有特例如果删除的是最后一个节点删除之后队列变空此时必须把 rear 也置为 NULL。否则 rear 会成为一个悬空的野指针指向一块已经被释放的内存。我在写这个项目时一开始出队函数只更新了 front忘记处理 rear结果在遍历到最后一层的最后一个节点时队列明明已经空了rear 还指着一个被 free 掉的节点。下一次入队时入队函数检查q-rear发现不为空就试图对一块已释放内存执行q-rear-next newNode段错误立刻出现。这个边界处理不是细节是链表队列能否正确工作的生死线。凡是写链表队列都必须把“空队列”、“单节点队列”、“删除最后一个节点”这三个状态穷举一遍任何一步漏掉都会在后续运行中爆发。2.3 “不用数组”到底省掉了什么有人可能会问既然题目说不用数组那我用 C 语言自带的malloc动态分配队列节点这算不算“用数组”显然不算。这里说的“数组”指的是在一块连续内存上用下标索引访问的线性结构而链表是靠指针把分散在堆里的节点串起来的非线性存储结构两者在内存布局上有本质区别。更准确地说“不用数组”这句话要表达的是三层意思不需要预先知道树的宽度也就没有“队列最大容量”这个概念。不需要下标运算只靠指针的 next 关系就能完成全部 FIFO 操作。不需要一次性申请大块连续内存每次只需要申请一个小节点释放时也按小节点归还。这第三点在内存碎片化严重的嵌入式系统里是实打实的优势。数组队列需要一次性申请一块完整的连续内存如果系统经过长时间运行堆被切割得七零八落一块几 KB 的连续空间可能根本分配不出来。链表队列则完全规避这个问题因为每次只申请一个结构体大小的空间成功率远高于大块连续分配。3. 实操代码实现与逐段拆解3.1 队列基础函数入队、出队、判空整个项目可以直接在标准 C 环境下编译运行不依赖任何第三方库。先写队列的基础操作这是后面所有功能的地基void enqueue(LinkQueue *q, TreeNode *tree) { QueueNode *n (QueueNode *)malloc(sizeof(QueueNode)); if (n NULL) { fprintf(stderr, malloc failed\n); exit(EXIT_FAILURE); } n-tree tree; n-next NULL; if (q-rear NULL) { // 队列为空首尾都指向新节点 q-front q-rear n; return; } q-rear-next n; // 挂到队尾 q-rear n; // 更新队尾指针 } TreeNode *dequeue(LinkQueue *q) { if (q-front NULL) return NULL; QueueNode *old q-front; TreeNode *tree old-tree; q-front q-front-next; // 头指针后移 if (q-front NULL) { // 出队后队列变空 q-rear NULL; } free(old); return tree; }malloc失败的处理我直接用exit终止了这是教学项目里最干脆的做法生产环境可以改成返回错误码或者走节点池复用逻辑后面踩坑章节会专门展开。这里有个细节值得注意dequeue返回的是TreeNode *并且是在free(old)之前从 old 节点里取出来的。如果你把顺序写反——先 free 再取指针——恭喜你提前获得一个野指针 bug。指针变量的生命周期和对它指向的内存的操作是两回事一定要先取出需要的数据再释放容器节点。3.2 基础版层序遍历主流程队列函数就绪之后层序遍历的核心代码非常短void levelOrderByLinkQueue(TreeNode *root) { if (root NULL) { printf(empty tree\n); return; } LinkQueue queue { NULL, NULL }; enqueue(queue, root); while (queue.front ! NULL) { TreeNode *cur dequeue(queue); printf(%d , cur-data); if (cur-left ! NULL) enqueue(queue, cur-left); if (cur-right ! NULL) enqueue(queue, cur-right); } printf(\n); }这段代码的逻辑用一个例子就能走通。假设有这样一棵树1 / \ 2 3 / \ \ 4 5 6 / 7执行过程如下操作出队元素打印入队操作出队后的队列状态初始--入队 1[1]循环111入队 2, 3[2, 3]循环222入队 4, 5[3, 4, 5]循环333入队 6[4, 5, 6]循环444无[5, 6]循环555入队 7[6, 7]循环666无[7]循环777无[]最终输出结果是1 2 3 4 5 6 7每一层的顺序完全正确。这背后的原理其实很朴素出队一个节点时把它的左右孩子按顺序排到队尾正好形成“先处理上一层、再处理下一层”的天然递进。这就是 BFS 在二叉树上的直观体现。3.3 分层打印增强版两种计数方案对比很多场景需要的不是一行平铺输出而是每一层单独一行。这个需求我在项目里也实现了而且试了两种不同口味。第一种方案最简单每一轮循环开始前先遍历一遍当前队列数出当前层有多少个节点然后按这个数量出队。void levelOrderLevelByLevel1(TreeNode *root) { if (root NULL) return; LinkQueue q { NULL, NULL }; enqueue(q, root); while (q.front ! NULL) { int levelSize 0; QueueNode *p q.front; while (p ! NULL) { // 扫描队列统计当前层节点数 levelSize; p p-next; } for (int i 0; i levelSize; i) { TreeNode *cur dequeue(q); printf(%d , cur-data); if (cur-left ! NULL) enqueue(q, cur-left); if (cur-right ! NULL) enqueue(q, cur-right); } printf(\n); } }这个方案好在思路直白容易理解但每次统计都要额外扫一遍队列。虽然统计的总开销摊下来仍是 O(n)却多了一次遍历指针的过程代码看着也不太优雅。第二种方案效率更高思路是维护两个计数器一个记录当前层剩余节点数一个记录下一层累计节点数。每出队一个节点当前层计数减一每入队一个节点下一层计数加一。当前层计数归零时说明这一层处理完了两层的计数对调然后输出换行符。void levelOrderLevelByLevel2(TreeNode *root) { if (root NULL) return; LinkQueue q { NULL, NULL }; int currentLevel 1; // 根节点所在层开始时只有 1 个节点 int nextLevel 0; enqueue(q, root); while (q.front ! NULL) { TreeNode *cur dequeue(q); printf(%d , cur-data); currentLevel--; if (cur-left ! NULL) { enqueue(q, cur-left); nextLevel; } if (cur-right ! NULL) { enqueue(q, cur-right); nextLevel; } if (currentLevel 0) { printf(\n); currentLevel nextLevel; nextLevel 0; } } }这两种方案用同一个测试树跑输出结果完全一致1 2 3 4 5 6 7就我个人偏好生产环境里我会选第二种因为它避免了一次额外扫描代码实际运行次数更少教学讲解时我会先用第一种因为它直接把“当前层节点数等于当前队列长度”这个核心观察讲透了。3.4 完整测试样例与输出验证项目里我写了一个标准的完整测试程序包含建树、遍历、释放三个环节#include stdio.h #include stdlib.h // 这里省略 3.1 和 3.2 节中定义的各类结构体与函数 TreeNode *makeNode(int data) { TreeNode *n (TreeNode *)malloc(sizeof(TreeNode)); n-data data; n-left n-right NULL; return n; } TreeNode *buildSampleTree(void) { TreeNode *root makeNode(1); root-left makeNode(2); root-right makeNode(3); root-left-left makeNode(4); root-left-right makeNode(5); root-right-right makeNode(6); root-left-right-left makeNode(7); return root; } void freeTree(TreeNode *root) { if (root NULL) return; freeTree(root-left); freeTree(root-right); free(root); } int main(void) { TreeNode *root buildSampleTree(); printf(基础版层序遍历: ); levelOrderByLinkQueue(root); printf(\n); printf(分层打印方法一:\n); levelOrderLevelByLevel1(root); printf(\n); printf(分层打印方法二:\n); levelOrderLevelByLevel2(root); freeTree(root); return 0; }编译命令很简单gcc -Wall -Wextra -g -o level_order main.c。-Wall -Wextra这两个编译选项强烈建议加上C 程序里大量的指针问题只有靠编译器警告和自己的检查结合才能尽早暴露。4. 复杂度对比与使用边界4.1 时间空间复杂度推演先从时间维度看。每个树节点恰好被入队一次、出队一次。入队操作是 O(1) 的尾部插入出队操作是 O(1) 的头部删除。所以整棵树遍历下来总时间复杂度是 O(n)n 是树中节点总数。这一点和数组队列没有任何区别链表方案没有劣化。再考虑分层打印的两个版本。方法一每一层开始时扫描一次队列扫描的节点总数等于当前层节点数所有层扫描总次数等于全树节点数所以总时间仍然是 O(n)。方法二的入队和出队操作同样是 O(1)额外维护两个计数器也是 O(1)总时间还是 O(n)。两个方法在渐进复杂度上完全一致只是常数存在差别。从空间维度看最关键的数据是“队列中任意时刻最多有多少个节点”。任何一次 while 循环开始时队列里存放的都是当前层的节点接下来这一层逐步出队下一层逐步入队。在这个过程的最极端瞬间队列里同时存在“当前层剩余节点”和“下一层已经入队的节点”总数量不超过当前层宽度加下一层宽度之和而上界是树的某一层最大宽度记为 w。如果树是完全二叉树w 约等于 n/2如果是退化链表树w 始终等于 1。所以空间复杂度是 O(w)或者更宽松地写 O(n)。这和“任何 BFS 都要付出 O(最大宽度) 辅助空间”的结论完全一致链表方案并没有减少空间复杂度它只是让这部分空间的分配方式变成了动态的、精确的——用多少申请多少。4.2 数组队列、链表队列、递归逐层三方案横向对照我把三种方案放在同一张表里对比了一次各自的性格差异一目了然对比维度数组队列链表队列递归逐层打印时间复杂度O(n)O(n)最坏 O(n²)空间复杂度O(w)但需要预设容量或扩容O(w)动态精确O(h) 栈空间 O(1) 额外是否需要预知树宽度需要否则扩容/浪费不需要不需要对递归深度的依赖无无高度限制深树会爆栈内存分配模式一次性大块多次小块无需堆分配适合场景快速原型的课堂练习嵌入式/无容器环境/深树教学演示小树这三者没有绝对谁优谁劣。数组队列胜在简单一个数组两个下标就能转起来链表队列胜在稳健不依赖连续内存和固定容量递归逐层打印胜在代码可读性高但性能和栈安全性都最差。4.3 真正应该用它的场景做完这个项目之后我给可以从中受益的目标场景画了个范围首先嵌入式开发是最大的受益方。裸机环境往往没有完整标准库更不可能有现成的动态数组容器链表队列用malloc加上 C 语言最基本的语法就能构建代价最小。其次深树遍历场景。树高度可能达到百万级时递归一定会爆栈数组队列无法预先知道宽度链表队列是唯一能自然容纳未知宽度的选择。再次面试和教学场景。很多面试官出这道题的目的不是让你实现 BFS而是验证你有没有吃透“队列是一种抽象底层可以用不同结构实现”这一层。如果你能顺手说清楚链式队列的入队出队边界条件和空间复杂度这一题基本就过了。5. 踩坑记录与调试技巧5.1 首尾指针的经典陷阱我在前面提过对 rear 指针处理不当的问题这里再展开一次。链表队列的绝大多数 bug 都出在首尾指针的一致性上这几乎是所有写链式队列的人都会踩的坑。我建议任何人在写完队列函数后都做一次“三状态测试”空队列入队、单节点队列出队、连续出队直到空。这三个状态的代码路径彼此独立只要有一个没覆盖就会在某个具体输入下炸出来。调试的时候有个小技巧不要只盯着出错的现场看而是在每一步操作后把 front 和 rear 打出来。如果出现front NULL但rear ! NULL或者反过来基本可以断定是边界状态没处理干净。把这两个指针的不变量记在心里排查效率会高很多。5.2 内存生命周期管理是第二道关卡这个项目涉及两类内存树节点的内存和队列节点的内存。两类内存必须分开管理生命周期需要严格分明。遍历开始前树节点已经被创建并且在堆上存在入队时队列节点被创建出来保存树节点的指针出队时队列节点被释放但树节点完全不受影响遍历结束后树节点仍存在需要单独释放。一图以蔽之队列节点是临时容器树节点是树本身谁都不该提前释放谁。我在项目初期犯过的错误是在 dequeue 里顺手把tree也给free了。这在遍历到倒数第二层时就会出现悬空指针——因为一个树节点被释放后它的父节点可能还在队列里等待被访问下一轮出队时拿到一个已经非法访问的地址。这个 bug 的隐蔽之处在于程序可能不会马上崩溃而是在某次极端输入下随机出现段错误极难排查。5.3 进一步优化节点池与“不用数组”的边界malloc和free每次调用都有开销而且频繁的小块分配释放会在堆上留下碎片。对嵌入式实时系统来说这两个问题都值得认真对待。我当时做的优化是引入“节点池”思路是队列节点本身只在遍历期间使用用完就释放与其反复 malloc/free不如维护一个空闲节点链表。出队时把节点插回空闲链表入队时优先从空闲链表取取不到才调用 malloc。// 伪代码示意 QueueNode *getQueueNode(TreeNode *tree) { QueueNode *n freePool; if (n ! NULL) { freePool freePool-next; } else { n (QueueNode *)malloc(sizeof(QueueNode)); } n-tree tree; n-next NULL; return n; } void releaseQueueNode(QueueNode *n) { n-next freePool; freePool n; }节点池化简了大量 malloc/free 调用遍历速度能提升不少。这个优化完全符合“不用数组”的约束因为它依然是链式结构没有开辟连续内存。但需要提醒一句节点池只适合“对象规格一致、生命周期短”的场景通用系统里过度使用反而会让代码难以理解。另外如果你的题目要求严格禁用任何“预分配”手段那节点池就得谨慎了。面试时最好先说清楚普通版本再补一句“如果性能要求高我可以用空闲链表做节点池复用”面试官通常会认为你考虑得足够成熟。5.4 一个更狠的实现思路树节点自身指针复用的边缘方案写项目时我还考虑过一种“完全不额外分配队列节点”的做法每一层节点在入队之前先把上一层的 left 和 right 指针临时借用为队列的 next 指针等遍历完当前层后边出队边恢复指针。这种方案理论上可以把辅助空间降到 O(1)代价是遍历过程中树结构被临时破坏。这个思路很有野心也很有面试观赏性但我不建议把它作为第一版交付。原因是恢复指针的顺序极容易出错错一个节点整棵树就废了调试成本远高于收益。如果真想尝试建议只在线索化二叉树或完美二叉树这种特殊结构里实验普通二叉树就先老老实实用独立队列节点。最后再分享一点实际体会做完整个项目我最深的体会是“层序遍历”和“链表”两个词放在一起没有表面上看起来那么违和。层序遍历本来就是一个关于顺序的算法队列负责维护顺序链表负责实现队列当你把“顺序”从“存储方式”里彻底剥离出来之后代码反而比教科书式的数组实现更容易说清楚每一步在干什么。如果你也需要在禁数组、禁递归的约束下实现层序遍历我的建议是把精力分成三份一份给队列的边界状态一份给内存的生命周期一份给遍历主流程。前两者解决的是“正确性”最后一项解决的是“完整性”。队列函数单独测试通过之后再套层序遍历逻辑基本一次就能跑通。这个思路适用于几乎所有“自定义数据结构 算法”组合的项目算是意外收获。