二叉树的层序遍历——AI 教会我的 BFS 面试必杀技

读完本文你将了解：二叉树层序遍历的两种写法 | BFS 队列模板的通用性 | 如何从一道题延伸到社交图谱遍历

📋 题目

原题：给你二叉树的根节点root，返回其节点值的层序遍历结果（即逐层地，从左到右访问所有节点）。

3 / \ 9 20 / \ 15 7

💡 先问一个问题

猜猜 AI 第一次写二叉树的层序遍历，它会怎么写？

大多数人（包括 AI）的第一反应是递归——因为平时写二叉树问题，90% 都是递归。但层序遍历偏偏是个异类：它天然适合迭代，不适合递归。

为什么呢？因为层序遍历需要"按层"输出，递归的调用栈天然是按深度走的，不是按层。

🤖 第一版：AI 的朴素尝试（用 DFS 硬做）

# AI 的第一反应：递归 + 层级参数deflevelOrder(root):result=[]defdfs(node,level):ifnotnode:returniflen(result)==level:result.append([])result[level].append(node.val)dfs(node.left,level+1)dfs(node.right,level+1)dfs(root,0)returnresult

AI 为什么会这样写？因为"带层级的递归"是大多数人能想到的最直观方案——用level参数标记当前深度，每层建一个数组。不能说它错，但面试官期待的不是这个。

复杂度：时间 O(n) 空间 O(h)（h = 树高，最坏 O(n)）

🧠 AI 的自我优化：队列才是正解

当我告诉 AI "面试官希望看到 BFS + 队列实现"后，AI 立刻给出了面试官真正想要的版本：

# AI 优化版：BFS + 队列fromcollectionsimportdequedeflevelOrder(root):ifnotroot:return[]result=[]queue=deque([root])whilequeue:level_size=len(queue)level=[]for_inrange(level_size):node=queue.popleft()level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)result.append(level)returnresult

关键技巧：level_size = len(queue)——每次循环开始时记录当前队列长度，这个长度恰好就是当前层的节点数。处理完这个数量的节点，就进入下一层。

复杂度：时间 O(n) 空间 O(w)（w = 最大层宽，最坏 n/2）

☕ Java 实现

classSolution{publicList<List<Integer>>levelOrder(TreeNoderoot){List<List<Integer>>result=newArrayList<>();if(root==null)returnresult;Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){intlevelSize=queue.size();List<Integer>level=newArrayList<>();for(inti=0;i<levelSize;i++){TreeNodenode=queue.poll();level.add(node.val);if(node.left!=null)queue.offer(node.left);if(node.right!=null)queue.offer(node.right);}result.add(level);}returnresult;}}

🎯 产品场景：朋友圈好友推荐

假设你正在开发一个社交 App，想让用户看到"可能认识的人"——分类为"一级好友"（直接好友）、“二级好友”（好友的好友）、“三级好友”。

这就是一个典型的 BFS 层序遍历问题：

deffriend_recommendations(graph,user,max_level=3):"""按亲密度推荐好友"""visited={user}queue=deque([user])level=0whilequeueandlevel<max_level:level_size=len(queue)level+=1print(f"=== 第{level}级好友 ===")for_inrange(level_size):current=queue.popleft()forneighboringraph[current]:ifneighbornotinvisited:visited.add(neighbor)queue.append(neighbor)print(f" 推荐:{neighbor}(第{level}度)")

同样逻辑可以套用到：文件系统目录层级展示、网络拓扑发现、知识图谱关联搜索。

📝 面试考点

高频变体题（面试常考）：

• LeetCode 107：自底向上层序遍历（最后reverse即可）
• LeetCode 103：锯齿形层序遍历（加个 flag 控制左右方向）
• LeetCode 429：N 叉树的层序遍历（把 left/right 换成 children）

参考资料

[1] LeetCode 102. Binary Tree Level Order Traversal: https://leetcode.com/problems/binary-tree-level-order-traversal/
[2] LeetCode 107. Binary Tree Level Order Traversal II: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
[3] LeetCode 103. Binary Tree Zigzag Level Order Traversal: https://leetcode.com/problems/binary-tree-level-order-traversal-zigzag/