- 正确答案：二叉树的层序遍历（也称广度优先遍历，BFS）是指按照从上到下、从左到右的顺序，逐层访问二叉树中所有节点的过程。其标准实现使用队列（FIFO结构）辅助完成：先将根节点入队；每次出队一个节点，访问它，并将其左右子节点（若存在）依次入队；重复该过程直至队列为空。 - 解答思路： 1. 初始化一个空队列，将根节点入队（若根为空则直接返回空结果）； 2. 循环处理队列：每次取出队首节点，将其值加入当前层结果列表； 3. 若该节点有左子节点，将左子节点入队；同理处理右子节点； 4. 为实现“按层分组”输出（如返回 List>），需在每轮循环开始前记录当前队列长度 len，表示本层节点数，然后仅对这 len 个节点执行出队+访问+子节点入队操作，从而确保每轮循环恰好处理一层； 5. 所有层处理完毕后，返回二维结果列表。 - 深度知识讲解：层序遍历本质是图的广度优先搜索在树结构上的特化应用。其正确性依赖于队列的先进先出特性——只有当第 k 层节点全部入队后，第 k+1 层节点才开始入队，且第 k 层节点必然在第 k+1 层节点之前被访问。底层数据结构选择至关重要：必须使用真正的队列（如 Java 中的 LinkedList 或 ArrayDeque，Python 中的 collections.deque），而非 list.pop(0)（时间复杂度 O(n)）。使用动态数组模拟队列时，需注意头指针移动或环形缓冲区设计以保证出队 O(1)。时间复杂度为 O(n)，每个节点访问且仅入队出队一次；空间复杂度最坏为 O(w)，w 是树的最大宽度（即某一层最多节点数），对于完全二叉树 w ≈ n/2；最好情况（退化为链表）为 O(1)。进阶考点常包括： • Z 字形遍历（奇数层正序、偶数层逆序）→ 在每层收集完后根据层数判断是否 reverse； • 每层返回平均值/最大值 → 在每层内遍历过程中维护 sum/max 变量； • 判断是否为完全二叉树 → 层序遍历时一旦遇到空节点，后续必须全为空； • 结合 parent 指针实现无队列 BFS（极少见，多用于内存受限场景）； • 与 DFS 的对比：DFS 使用栈（递归隐式栈或显式栈），空间复杂度 O(h)，h 为树高，适合路径相关问题（如求路径和、最近公共祖先）；BFS 天然支持最短路径语义（如最小深度、最小编辑距离树形变体）。 - 伪代码（带层分组）： ``` function levelOrder(root): if root is null: return empty list of lists result = empty list of lists queue = new deque() queue.push(root) while queue is not empty: levelSize = queue.size() // 当前层节点总数 currentLevel = empty list for i from 0 to levelSize - 1: node = queue.popLeft() // 出队队首 currentLevel.append(node.val) if node.left is not null: queue.pushRight(node.left) if node.right is not null: queue.pushRight(node.right) result.append(currentLevel) return result ``` - Java 实现片段（关键部分）： ``` public List> levelOrder(TreeNode root) { List> result = new ArrayList<>(); if (root == null) return result; Queue queue = new ArrayDeque<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); List level = new ArrayList<>(levelSize); // 预分配容量 for (int i = 0; i < levelSize; i++) { TreeNode node = 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); } return result; } ``` - Python 实现片段（使用 deque）： ``` from collections import deque def levelOrder(root): if not root: return [] result = [] queue = deque([root]) while queue: level_size = len(queue) level = [] for _ in range(level_size): node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result ``` - 常见错误提醒： • 错误地在 for 循环中用 queue.size() 动态判断条件（因循环中 size 变化导致提前退出或越界）→ 必须在循环外缓存初始 size； • 忘记判空 root 导致 NullPointerException / AttributeError； • 使用 list.pop(0) 替代 deque.popleft()，使单次出队退化为 O(n)，整体复杂度升至 O(n²)； • 将左右子节点入队顺序颠倒（虽不影响层序性质，但违反“从左到右”要求，面试中会被扣分）。

阿里实习 AI Infra面经

全站热榜

创作者周榜