一、题目描述给你二叉树的根节点root返回其节点值的层序遍历即逐层地从左到右访问所有节点。示例输入root [3,9,20,null,null,15,7] 输出[[3],[9,20],[15,7]]对应树结构3 / \ 9 20 / \ 15 7二、为什么这道题值得学这道题是BFS 的入门标杆也是面试必考题。它考察的核心在于遍历思维从“一条路走到黑”DFS转变为“一圈一圈向外扩”BFS。数据结构对队列Queue 特性的理解与应用。细节处理如何优雅地分隔每一层的数据这是最容易翻车的地方。三、核心思想队列 分层截断层序遍历的本质是广度优先搜索BFS。想象你在往湖里扔石头水波纹是一圈圈往外扩散的这就叫“层序”。为了实现这种效果我们使用队列根节点入队。当队列不为空时取出队首元素访问这一层的节点。将该节点的左右子节点依次入队为下一层做准备。重复步骤 2直到队列为空。⚠️ 难点突破如何区分“层”如果不加控制队列里会混着当前层和下一层的节点。解决方案是记录当前层的节点数量levelSize。在每一层开始遍历前先获取当前队列的长度size()。这个size就是当前层的节点数。我们只循环size次这期间出队的节点一定都是同一层的。四、解法一迭代法BFS面试首选 ✅思路图解以[3,9,20,null,null,15,7]为例步骤操作队列状态 (队头→队尾)结果集初始3 入队[3][]第1层size1, 弹出3, 加入9, 20[9, 20][[3]]第2层size2, 弹出9(无子), 弹出20, 加入15, 7[15, 7][[3], [9, 20]]第3层size2, 弹出15(无子), 弹出7(无子)[][[3], [9, 20], [15, 7]]Java 实现class Solution { public ListListInteger levelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) { return result; } QueueTreeNode queue new LinkedList(); queue.offer(root); // 根节点入队 while (!queue.isEmpty()) { int levelSize queue.size(); // 关键点获取当前层节点数 ListInteger levelList new ArrayList(); // 遍历当前层的所有节点 for (int i 0; i levelSize; i) { TreeNode curNode queue.poll(); levelList.add(curNode.val); // 将下一层的节点加入队列 if (curNode.left ! null) { queue.offer(curNode.left); } if (curNode.right ! null) { queue.offer(curNode.right); } } result.add(levelList); } return result; } }复杂度分析时间复杂度O(N)每个节点恰好被访问一次。空间复杂度O(N)最坏情况下树完全平衡队列中最多存储 N/2 个节点最后一层的节点数。五、解法二递归法DFS拓展思维虽然层序遍历是 BFS 的典型应用但我们也可以用 DFS前序遍历来实现。核心思路在递归时携带一个参数level层数。只要知道节点在第几层就能把它放进结果集对应的位置。Java 实现class Solution { private ListListInteger result new ArrayList(); public ListListInteger levelOrder(TreeNode root) { dfs(root, 0); return result; } private void dfs(TreeNode node, int level) { if (node null) { return; } // 如果当前层还没有初始化先创建一个空列表 if (result.size() level) { result.add(new ArrayList()); } // 将当前节点加入对应层 result.get(level).add(node.val); // 递归处理左右子树层数1 dfs(node.left, level 1); dfs(node.right, level 1); } }面试点评这种方法代码简洁但不够直观且使用了递归栈空间复杂度取决于树的高度 O(H)。面试官通常更希望看到你对队列/BFS 的掌握。六、常见错误与避坑指南❌错误一直接while(!queue.isEmpty())而不记录levelSize这会导致你把不同层的节点混在一个 List 里。❌错误二在 for 循环中调用queue.size()// 错误示例 for(int i 0; i queue.size(); i) { ... }因为在循环体内你加入了新的子节点queue.size()会动态变化导致循环次数出错。一定要先存下来int levelSize queue.size();❌错误三混淆 DFS 和 BFSDFS 用栈递归隐式使用栈适合找路径、判断深度。BFS 用队列适合找最短路径、层序遍历。七、面试高频追问1️⃣如果要求从下往上的层序遍历呢LeetCode 107很简单在 BFS 方法中每次result.add(levelList)改为result.add(0, levelList)头部插入或者最后执行Collections.reverse(result)。2️⃣如果要求之字形打印呢LeetCode 103在 BFS 基础上加一个标志位isOrderLeft。如果是 true正常加入 List如果是 false使用LinkedList.addFirst()倒序加入。3️⃣BFS 和 DFS 哪个更快时间复杂度都是 O(N)。但在空间上BFS 占用内存通常更大队列存储DFS 占用栈空间通常比队列小除非树极不平衡。八、总结与关联回到我们的刷题系列LeetCode 104/543重点在于DFS后序遍历关注深度和高度。LeetCode 102重点在于BFS层序遍历关注广度和平级关系。记忆口诀层序遍历靠队列记录长度分层退DFS 递归带层数添加位置要对路。
LeetCode 102：二叉树的层序遍历 —— 从 DFS 到 BFS 的思维跃迁
一、题目描述给你二叉树的根节点root返回其节点值的层序遍历即逐层地从左到右访问所有节点。示例输入root [3,9,20,null,null,15,7] 输出[[3],[9,20],[15,7]]对应树结构3 / \ 9 20 / \ 15 7二、为什么这道题值得学这道题是BFS 的入门标杆也是面试必考题。它考察的核心在于遍历思维从“一条路走到黑”DFS转变为“一圈一圈向外扩”BFS。数据结构对队列Queue 特性的理解与应用。细节处理如何优雅地分隔每一层的数据这是最容易翻车的地方。三、核心思想队列 分层截断层序遍历的本质是广度优先搜索BFS。想象你在往湖里扔石头水波纹是一圈圈往外扩散的这就叫“层序”。为了实现这种效果我们使用队列根节点入队。当队列不为空时取出队首元素访问这一层的节点。将该节点的左右子节点依次入队为下一层做准备。重复步骤 2直到队列为空。⚠️ 难点突破如何区分“层”如果不加控制队列里会混着当前层和下一层的节点。解决方案是记录当前层的节点数量levelSize。在每一层开始遍历前先获取当前队列的长度size()。这个size就是当前层的节点数。我们只循环size次这期间出队的节点一定都是同一层的。四、解法一迭代法BFS面试首选 ✅思路图解以[3,9,20,null,null,15,7]为例步骤操作队列状态 (队头→队尾)结果集初始3 入队[3][]第1层size1, 弹出3, 加入9, 20[9, 20][[3]]第2层size2, 弹出9(无子), 弹出20, 加入15, 7[15, 7][[3], [9, 20]]第3层size2, 弹出15(无子), 弹出7(无子)[][[3], [9, 20], [15, 7]]Java 实现class Solution { public ListListInteger levelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) { return result; } QueueTreeNode queue new LinkedList(); queue.offer(root); // 根节点入队 while (!queue.isEmpty()) { int levelSize queue.size(); // 关键点获取当前层节点数 ListInteger levelList new ArrayList(); // 遍历当前层的所有节点 for (int i 0; i levelSize; i) { TreeNode curNode queue.poll(); levelList.add(curNode.val); // 将下一层的节点加入队列 if (curNode.left ! null) { queue.offer(curNode.left); } if (curNode.right ! null) { queue.offer(curNode.right); } } result.add(levelList); } return result; } }复杂度分析时间复杂度O(N)每个节点恰好被访问一次。空间复杂度O(N)最坏情况下树完全平衡队列中最多存储 N/2 个节点最后一层的节点数。五、解法二递归法DFS拓展思维虽然层序遍历是 BFS 的典型应用但我们也可以用 DFS前序遍历来实现。核心思路在递归时携带一个参数level层数。只要知道节点在第几层就能把它放进结果集对应的位置。Java 实现class Solution { private ListListInteger result new ArrayList(); public ListListInteger levelOrder(TreeNode root) { dfs(root, 0); return result; } private void dfs(TreeNode node, int level) { if (node null) { return; } // 如果当前层还没有初始化先创建一个空列表 if (result.size() level) { result.add(new ArrayList()); } // 将当前节点加入对应层 result.get(level).add(node.val); // 递归处理左右子树层数1 dfs(node.left, level 1); dfs(node.right, level 1); } }面试点评这种方法代码简洁但不够直观且使用了递归栈空间复杂度取决于树的高度 O(H)。面试官通常更希望看到你对队列/BFS 的掌握。六、常见错误与避坑指南❌错误一直接while(!queue.isEmpty())而不记录levelSize这会导致你把不同层的节点混在一个 List 里。❌错误二在 for 循环中调用queue.size()// 错误示例 for(int i 0; i queue.size(); i) { ... }因为在循环体内你加入了新的子节点queue.size()会动态变化导致循环次数出错。一定要先存下来int levelSize queue.size();❌错误三混淆 DFS 和 BFSDFS 用栈递归隐式使用栈适合找路径、判断深度。BFS 用队列适合找最短路径、层序遍历。七、面试高频追问1️⃣如果要求从下往上的层序遍历呢LeetCode 107很简单在 BFS 方法中每次result.add(levelList)改为result.add(0, levelList)头部插入或者最后执行Collections.reverse(result)。2️⃣如果要求之字形打印呢LeetCode 103在 BFS 基础上加一个标志位isOrderLeft。如果是 true正常加入 List如果是 false使用LinkedList.addFirst()倒序加入。3️⃣BFS 和 DFS 哪个更快时间复杂度都是 O(N)。但在空间上BFS 占用内存通常更大队列存储DFS 占用栈空间通常比队列小除非树极不平衡。八、总结与关联回到我们的刷题系列LeetCode 104/543重点在于DFS后序遍历关注深度和高度。LeetCode 102重点在于BFS层序遍历关注广度和平级关系。记忆口诀层序遍历靠队列记录长度分层退DFS 递归带层数添加位置要对路。
