层序遍历本来不算难题但题目一旦加上两个限制——不用数组、不用递归——难度立刻变了。很多人第一反应是层序不就是BFS吗BFS不就是队列吗队列用数组模拟不是很自然吗为什么非要绕道链表我最初也有同样的疑问。后来在学习和调试中才意识到这个限制不是在故意刁难而是在逼你把“队列到底是什么”想清楚。链表实现层序遍历的核心功课不是树的遍历本身而是如何用一个链式队列把每一层的节点按顺序“接住”再“吐出来”。这篇文章我不会只贴代码我会把设计思路、边界条件、踩过的坑一起写完适合正在学二叉树和BFS的读者也适合想在面试里把这个考点讲清楚的人。1. 为什么“链表层序遍历”这个组合值得单独写一篇层序遍历的本质是按“层”的维度处理节点树的前序、中序、后序都可以靠递归轻松搞定唯独层序和递归天然不对付。这不是实现能力的问题而是思考模型的问题。把这两件事掰开看你才能真正理解为什么链表队列是这个场景里一个非常合理的答案。1.1 递归看着能做其实天生不对路递归的特点是深度优先它沿着一条分支一路扎到底再退回来走另一条分支。前序、中序、后序本质上都是“一条路走到黑再回溯”的路线和递归的执行模型完全吻合。层序则要求你先把根节点处理完再处理它的两个孩子然后处理四个孙子一层一层向四周扩散。用递归硬写层序最笨的办法是带上一个层级参数递归到每一层时把节点挂到对应的层列表里。这个思路可行但它不是真正的广度优先遍历访问顺序依然是深度优先的只是最后把结果按层归了类。更麻烦的是它必须额外维护一个“层号到下标的映射”这个映射十有八九就是数组或者哈希表。题目说“不使用数组”时这种方案直接出局。还有个隐患是递归深度。二叉树在最坏情况下会退化成一条链树高等于节点数。如果节点有几千甚至几万递归层数可能直接压爆函数调用栈。层序本身是迭代思维硬用递归去模拟属于把简单问题复杂化。1.2 数组队列最常用但不总是最优教科书里讲层序遍历几乎都是数组模拟队列开一个数组rear指针负责入队front指针负责出队循环利用空间时再套一层取模运算。这套方案简单、直观、缓存友好90%的情况下我都推荐它。但它有几个隐藏问题。第一容量不灵活。静态数组必须提前指定大小而二叉树每一层的最大宽度可能差很多开小了会溢出开大了浪费内存。第二动态扩容有代价。如果让数组自动增长扩一次就要搬移数据虽然均摊成本不高但内存反复分配和搬移在嵌入式环境、实时系统里是能感知到的开销。第三如果考官或题目有意考察你对链表的掌握数组方案就变成“会被直接否决的答案”。所以题目特意加“不使用数组”这个条件本质上是在考察你会不会用链表组织数据。链表天然没有容量上限插入和删除都在常数时间内完成非常契合“队列长度会动态变化”的场景。1.3 链表队列的位置灵活性与可控性链表队列的核心思想非常简单每个节点不仅存数据还存一个指向下一个节点的指针队列只需要记住头节点和尾节点就能做到O(1)入队、O(1)出队。放在层序遍历这个场景里链表队列还有一个隐藏优势因为数据是用节点串联的你可以在不移动元素的前提下任意遍历一遍当前队列的内容。举个例子如果你想知道当前层还有多少个节点没有处理数组方案需要用rear减front再取模链表方案直接从头指针走到尾指针数一下就行。这个特性在后面的“按层输出”和“每层最大值”会派上大用场。2. 链式队列的骨架先把手里的工具磨利层序遍历的主逻辑只有十几行但队列本身必须写扎实。很多人的问题恰恰出在队列的边界处理上所以我建议把链式队列当作一个独立模块来设计和验证跑通之后再套用到树上。2.1 三个结构体的分工用C语言做演示最直观因为它强迫你面对指针和内存。下面这三个结构体是整个方案的地基。typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; typedef struct QueueNode { TreeNode *data; struct QueueNode *next; } QueueNode; typedef struct Queue { QueueNode *front; QueueNode *rear; } Queue;TreeNode是二叉树节点这个没什么好说的。QueueNode是队列的节点它包装的是TreeNode的指针而不是TreeNode的拷贝这样可以避免复制整棵树出队时也只移动指针。Queue结构体是队列的“头部信息”只存两个指针front指向队首rear指向队尾。你可能想问为什么非要单独包一个Queue结构体直接用两个全局QueueNode指针不就行了单独封装的好处是初始化、传参、判空都变得明确。比如判空只需要看q-front是否为NULL而不用同时管理两个全局变量也不容易出现头尾不同步的问题。2.2 入队尾巴上做文章入队操作是在链表尾部追加节点。因为rear指针永远指向最后一个节点所以追加动作是O(1)的。void enqueue(Queue *q, TreeNode *node) { QueueNode *newNode (QueueNode *)malloc(sizeof(QueueNode)); newNode-data node; newNode-next NULL; if (q-rear NULL) { q-front newNode; q-rear newNode; } else { q-rear-next newNode; q-rear newNode; } }这里的关键分支是“这个队列是不是本来就为空”。如果rear是NULL说明队列里一个节点都没有新节点既是队首也是队尾front和rear都要指向它。如果队列不为空那就把新节点挂到当前尾节点的next上然后把rear更新成新节点。顺序不能反先连接再移指针。有个细节值得注意newNode-next必须显式置为NULL。如果用malloc申请内存这块内存里的内容是随机的不手动置空新节点后面可能挂着一个野指针到时候遍历队列会直接越界。这个坑我踩过排查的时候一度怀疑是遍历逻辑的问题结果是最初没有初始化next字段。2.3 出队头部的释放陷阱出队则是从头节点取走数据然后让front指向下一个节点。TreeNode *dequeue(Queue *q) { if (q-front NULL) return NULL; QueueNode *tmp q-front; TreeNode *node tmp-data; q-front q-front-next; if (q-front NULL) { q-rear NULL; } free(tmp); return node; }最容易忘的是中间那个if出队之后如果front变成了NULL说明队列已经空了此时必须把rear也置成NULL。为什么因为rear还指着刚刚被释放的那个旧节点这个指针已经成为悬垂指针。如果不清空下一次入队时会走else分支对已经free掉的节点做q-rear-next newNode这就是典型的未定义行为程序可能在某个不起眼的地方崩溃。出队函数返回的是TreeNode指针也就是从队列里取出来的二叉树节点。拿到之后层序遍历就能对这个节点做访问和处理了。3. 遍历主体出队、访问、入队循环里的三连击队列工具备好之后层序遍历本体就是一场接力赛。根节点先入场然后每次从队首取一个节点访问它再把它的左右孩子从队尾放进去。只要队列里还有节点就继续这个循环。3.1 三个动作的循环逻辑层序遍历的循环可以压缩成三个动作出队从队首取出当前要处理的节点。访问打印节点值或者做其他业务处理。入队把当前节点的左孩子和右孩子依次放入队尾。这组动作的意义在于队列天然保存了“下一批要处理的节点”。假设处理的是根节点出队后我们把它的两个孩子入队此时队列里就是第二层从左到右的两个节点。下一次循环先取出左孩子处理它时把左孩子的两个孩子放到队尾再接右孩子处理它时把右孩子的两个孩子继续往队尾放。每一层节点入队时都排在上一层还没处理的节点之后所以出队顺序自然就是层序顺序。你不需要额外记录任何路径信息也不需要回溯队列本身就把“从哪里继续”这个状态保存了。3.2 完整代码基础版#include stdio.h #include stdlib.h void initQueue(Queue *q) { q-front NULL; q-rear NULL; } int isEmpty(Queue *q) { return q-front NULL; } void levelOrderTraversal(TreeNode *root) { if (root NULL) return; Queue q; initQueue(q); enqueue(q, root); while (!isEmpty(q)) { TreeNode *cur dequeue(q); printf(%d , cur-val); if (cur-left ! NULL) { enqueue(q, cur-left); } if (cur-right ! NULL) { enqueue(q, cur-right); } } printf(\n); }注意开头对空树的判断。如果root是NULL直接返回否则入队一个NULL后面dequeue时就会对空指针解引用程序当场崩溃。这种防护看起来简单但在实际代码里很容易漏。队列节点和树节点是两类不同的内存队列节点在出队时用free释放树节点是用户自己的树结构遍历过程中不能动它。释放次序和内存责任划分我会在第六节展开。3.3 用一个三层二叉树走一遍我们来手动演算一棵树1 / \ 2 3 / \ \ 4 5 6队列初始化front - [1]。 入队1队列[1]。 出队1打印“1”。左孩子2入队右孩子3入队队列[2, 3]。 出队2打印“2”。左孩子4入队右孩子5入队队列[3, 4, 5]。 出队3打印“3”。右孩子6入队队列[4, 5, 6]。 出队4打印“4”。无子节点。 出队5打印“5”。无子节点。 出队6打印“6”。无子节点。 队列空结束。最终输出是1 2 3 4 5 6。整个过程没有任何递归调用也没有使用数组存储节点。可以看到队列在这里承担了全部“待办事项”的记账工作而链表则让这笔账可以无限记下去不必预先分配空间。4. 按层输出的两条路队列长度统计与NULL哨兵上一节的代码能把所有节点按层序打印出来但输出是一整行看不出谁属于哪一层。很多场景要求“每一层输出一行”或者要求单独处理每一层的边界比如找每层最大值、右视图等。这时候就需要在遍历过程中感知层的切换。主要有两种做法。4.1 计数法入队前先盘点计数法的核心洞察是在每一层的处理开始时队列里恰好存放着当前层的全部节点。这是层序遍历的天然性质因为上一层节点全部出队之后新入队的全部是下一层节点。所以我们可以先在链表里数一遍当前队列有多少个节点记为cnt然后只出队cnt次。这cnt次出队对应的就是完整的一层。每出队一个节点再把它的孩子入队那些孩子是下一层的成员不会影响当前层的出队次数。void levelOrderWithLevel(TreeNode *root) { if (root NULL) return; Queue q; initQueue(q); enqueue(q, root); int level 0; while (!isEmpty(q)) { int cnt 0; QueueNode *p q.front; while (p ! NULL) { cnt; p p-next; } printf(Level %d: , level); for (int i 0; i cnt; i) { TreeNode *cur dequeue(q); printf(%d , cur-val); if (cur-left ! NULL) enqueue(q, cur-left); if (cur-right ! NULL) enqueue(q, cur-right); } printf(\n); level; } }为什么用链表统计长度比数组队列方便数组队列需要(rear - front capacity) % capacity来计算元素个数不仅要考虑循环取模还要处理rear小于front的情况链表队列则直接从头走到尾代码直白也不存在取模边界。这就是“用对数据结构”带来的红利。计数法的通用性很强后面讲“每层最大值”“右视图”时都要用到它。4.2 哨兵法向队列里塞一个NULL另一种做法是往队列里插入一个特殊标记表示“这一层结束了”。通常的做法是在根节点入队后再入队一个NULL。void levelOrderWithSentinel(TreeNode *root) { if (root NULL) return; Queue q; initQueue(q); enqueue(q, root); enqueue(q, NULL); while (!isEmpty(q)) { TreeNode *cur dequeue(q); if (cur NULL) { printf(\n); if (isEmpty(q)) break; enqueue(q, NULL); } else { printf(%d , cur-val); if (cur-left ! NULL) enqueue(q, cur-left); if (cur-right ! NULL) enqueue(q, cur-right); } } }哨兵法的思路是每遇到一个NULL就知道一层结束了输出换行然后重新在队尾补一个NULL作为下一层的结束标记。为什么能确定下一层一定存在节点因为如果队列已经空了说明所有层都处理完直接break如果队列不为空说明还有下一层节点在排队此时补一个NULL放在它们后面刚刚好。这里有三个边界必须处理好根节点入队后必须马上入队NULL不能等。遇到NULL时要先判断队列是否已空再决定是否补哨兵否则会在空队列上再入队一个NULL形成死循环。哨兵节点本身不占用树节点空间它就是dequeue返回的NULL所以出队时不需要对NULL做树操作。4.3 什么时候选哪种从效果上看计数法和哨兵法都能实现按层输出。区别在于计数法不依赖特殊值逻辑更“正统”而且能直接知道当前层的宽度对后续计算最大值、平均值非常友好。哨兵法实现代码短一些但需要依赖“节点值不可能等于NULL”这个约定。如果未来某天你想往队列里塞真正的NULL节点数据这个方案就崩了。我的建议是面试和实际项目中优先用计数法。它多了一次链表遍历的开销但这正是链表的特性而且很多场景本来就还需要统计当前层的信息一次遍历顺便把层宽也算出来了何乐而不为。5. 选型对比数组队列、链表队列、递归模拟各算一笔账写到这里有必要把几种方案放在一起做个定量对比方便你在不同场景里做选择。表里的“容量”指的是队列能容纳的节点数上限。维度数组循环队列链表队列递归模拟容量限制固定容量或需要扩容理论上无上限无容量问题入队/出队复杂度O(1)但取模运算有额外开销O(1)含malloc/free开销不涉及队列空间占用连续内存可能有闲置槽位每个节点多一个指针开销函数调用栈层数据容器栈溢出风险无无树高过大时明显实现难度低中重视指针边界中代码绕获取当前层宽度需要取模计算直接遍历链表数数需要额外容器缓存局部性好差不适用从表格能看出数组队列在绝大多数场景里是最平衡的链表队列的主要成本来自节点内存分配和指针跳转的缓存不友好。但链表队列有两个场景无可替代一是队列长度变化幅度大且未知二是不想预先估算内存。递归模拟层序看起来代码可能挺短比如用哈希表按层收集节点但它的空间账并不划算既要承担递归栈的深度开销又要额外维护一个按层分类的容器。层序遍历本身只需要O(n)空间队列里最多存n个节点递归模拟的常数项往往更高。所以我的选型建议是默认用数组循环队列如果题目明确禁用数组、或者树的形状极度“不可预测”就换链表队列。至于递归模拟它更适合出现在“证明递归为什么不适合BFS”的讨论里而不是作为正式实现方案。6. 链式队列层序遍历的翻车现场与排查链路链式队列的代码不多但指针操作密集翻车点非常集中。这里记录四个我在调试中最常遇到的状态以及对应的排查思路。6.1 rear指针没回收第二次入队直接悬垂症状第一次入队、出队都正常循环到第二层时程序突然崩溃或者某个节点值变成垃圾数据。排查思路检查dequeue里有没有在front为空时同步把rear置空。如果少了这个分支第一次出队后rear仍然指向已经被free掉的节点。第二次enqueue时代码走else分支执行q-rear-next newNode这实际上是在向已经释放的内存里写指针。这个bug在单节点树或者只处理一层时不会暴露因为队列还没空就结束了。一旦树有两层以上第二次入队必炸。我在调试时一度以为是树建错了打印了一堆地址才定位到队列的头尾指针不同步。6.2 左右孩子判空不到位NULL被塞进队列症状遍历过程中偶发崩溃而且只在某些树的形态下崩溃。排查思路检查入队前有没有判断left和right是否为NULL。如果某个节点只有一个孩子不判空就把NULL入队那么下次dequeue时cur就是NULL执行printf(%d , cur-val)直接解引用空指针。 更隐蔽的问题是这种bug在完全二叉树里反而不容易暴露因为完全二叉树每个节点都有左右孩子或都为叶子。一旦遇到“只有右孩子没有左孩子”的树问题立刻出现。6.3 先出队再统计层数全乱了症状使用计数法按层输出时第二层开始节点数量不对有时把下一层的节点也打到了当前行。排查思路回想一下层序遍历的过程。出队一个当前层节点后会立刻把它孩子入队。如果先出队再统计队列长度统计到的数字里已经混入了下一层节点当前层的节点数就被高估了。正确顺序一定是先统计链表长度再开始出队循环。这个顺序千万不要反过来。这个问题的本质是“队列的长度在动态变化”。统计动作必须发生在“当前层全部存在且下一层尚未入队”的时间窗口也就是while循环开始的那一刻。6.4 内存释放的节奏问题症状程序运行正常但用内存检测工具跑一遍发现大量节点泄漏或者反过来遍历完再操作树节点时发现内容已被清空。排查思路要分清两类内存的所有权。队列节点由队列内部管理dequeue之后应该立即free。如果你只改指针不移除节点或者忘了free每遍历一个节点就泄漏一块内存。树节点所有权在调用方手里。层序遍历只负责“读”必须在dequeue返回TreeNode指针后原样保留不能误释放。如果在遍历循环里对cur调了free后续使用这棵树的功能就可能读到失效数据。在实际工程里我倾向于把“树的销毁”和“队列的销毁”彻底分开各写各的函数。队列的释放跟着dequeue走树的释放用递归或单独的后序遍历两个模块不要交叉。7. 同一个骨架的三道衍生题锯齿遍历、每层最大值、右视图层序遍历的骨架练熟了下面这几道题就只是在小循环里做局部调整。同一套链表队列稍微改一下访问逻辑就能应付不同需求。7.1 锯齿遍历加一个方向开关锯齿遍历要求第一层从左到右第二层从右到左第三层再从左到右交替进行。基于计数法的按层遍历你可以在每一层都拿到当前层的全部节点然后决定正向还是反向输出。如果还是坚持“不用数组”那么最自然的做法是用两个链表栈交替。一个栈保存当前层另一个栈保存下一层同时用一个布尔变量记录当前方向。当前层如果是“从左到右”那下一层入栈时就先压左孩子再压右孩子这样弹出顺序就是从右到左当前层如果是“从右到左”下一层就反过来先压右孩子再压左孩子。等当前层节点全部出栈交换两个栈取反方向标志继续下一轮。这个变种的价值在于它证明了“无数组、无递归”的限制下你依然能做层序相关的复杂操作只是需要额外一个栈结构。链式栈本质上就是头插法的链表和链式队列共享同一套指针思维。7.2 每层最大值计数法的直接红利要输出每一层的最大值只需要在计数法的基础上加一个max变量在每一层出队时逐个比较。for (int i 0; i cnt; i) { TreeNode *cur dequeue(q); if (i 0 || cur-val max) { max cur-val; } if (cur-left ! NULL) enqueue(q, cur-left); if (cur-right ! NULL) enqueue(q, cur-right); } printf(level %d max: %d\n, level, max);如果没有先统计cnt你要判断“当前节点是不是本层第一个节点”就会很别扭。有了cnti等于0就是一层开始这个边界判断变得非常干净。类似地每层平均值只需要累计sum然后除以cnt每层中位数则需要把本层节点收集起来排序这时单纯靠链表队列就有点吃力了适合引入缓冲数据。数据结构选型永远是跟着需求走的。7.3 右视图只要每层的最后一个节点右视图要求输出从右侧看到的节点也就是每一层最右边的那个节点。这个需求在二叉树上有个小陷阱最右边的节点不一定是右孩子链上的节点比如右孩子为空时视线的落点会变成左子树的某个深层节点。用层序思维解决就完全不用纠结树的形态for (int i 0; i cnt; i) { TreeNode *cur dequeue(q); if (i cnt - 1) { printf(%d , cur-val); } if (cur-left ! NULL) enqueue(q, cur-left); if (cur-right ! NULL) enqueue(q, cur-right); }当i等于cnt减1时当前节点就是这一层最后访问的那个节点也就是右视图里应该出现的节点。左视图同理把条件改成i等于0就行。这道题是“层宽度信息”价值的最直观体现。8. 最后的一点个人看法链表实现层序遍历这个题目与其说是考二叉树不如说是考你能不能把一个数据结构用到位。队列是层序的骨架链表是队列的骨架两者组合起来既绕开了递归的栈深度问题也避开了数组容量限制。我在实际中更常用数组循环队列因为大部分业务场景节点数可控、内存连续、性能更好。但链表队列的价值在于它提醒我当限制条件改变时不要抱怨题目刁钻而是要顺着约束重新思考方案。如果你正在学习这个知识点建议不要只抄代码。先把队列单独实现一遍用几个不同形状的树测试再去跑层序遍历。等你亲手调过两次悬垂指针见过一次统计顺序导致的错乱这个知识点才算真正长在你身上。
