- 正确答案：二叉树层序遍历（又称广度优先遍历，BFS）是指按树的层级从上到下、从左到右依次访问每个节点。其标准实现使用队列（FIFO结构）辅助：根节点入队；每次出队一个节点，访问它，并将其左右子节点（若存在）依次入队；重复该过程直至队列为空。 - 解答思路： 1. 初始化一个空队列，将根节点入队； 2. 当队列非空时，执行循环： a. 出队一个节点，记录其值（即“访问”）； b. 若该节点有左子节点，将其入队； c. 若该节点有右子节点，将其入队； 3. 循环结束，所有节点按层序被访问完毕。若需按层分组返回（如返回 List>），则需在每轮循环中一次性处理当前层全部节点——即在每次外层循环开始前记录队列当前长度 len，然后连续出队 len 次，期间将子节点加入队列但不混入本层处理。 - 深度知识讲解：层序遍历的本质是图的广度优先搜索在树（无环连通有向无权图）上的特例。队列的选择源于BFS的天然需求：先访问的节点应优先扩展其邻接点，而树中邻接点即为子节点，且必须保证同层节点在下一层节点之前被处理。底层实现中，队列通常用数组模拟的循环队列或语言内置双端队列（如Java的ArrayDeque、Python的collections.deque），避免使用链表或list.pop(0)（后者在Python中为O(n)时间）。时间复杂度为O(n)，其中n为节点总数，因每个节点入队、出队各一次；空间复杂度最坏为O(w)，w为树的最大宽度（如完全二叉树最后一层约n/2个节点），对应队列峰值容量。对比深度优先遍历（DFS），层序遍历无法仅靠递归自然表达（递归天然是栈式、深度优先），必须显式使用队列这一迭代结构，体现了数据结构选择对算法形态的根本约束。进阶考点常包括： • Z字形层序遍历（奇数层正序、偶数层逆序）→ 引入双端队列或每层结果后翻转； • 层序遍历构建一维数组表示的完全二叉树（如堆）→ 利用索引关系：i号节点的左子为2i+1，右子为2i+2； • 结合层高信息计算直径、最大宽度、是否为完全二叉树等——均依赖层序中天然携带的层级编号或位置信息。 - 伪代码（基础层序，返回一维列表）： ``` function levelOrder(root): if root is null: return empty list queue = new Queue() result = empty list queue.enqueue(root) while not queue.isEmpty(): node = queue.dequeue() result.append(node.val) if node.left is not null: queue.enqueue(node.left) if node.right is not null: queue.enqueue(node.right) return result ``` - 伪代码（分层返回，返回二维列表）： ``` function levelOrderByLevel(root): if root is null: return empty list of lists queue = new Queue() result = empty list of lists queue.enqueue(root) while not queue.isEmpty(): levelSize = queue.size() // 当前层节点数 currentLevel = empty list for i from 0 to levelSize - 1: node = queue.dequeue() currentLevel.append(node.val) if node.left is not null: queue.enqueue(node.left) if node.right is not null: queue.enqueue(node.right) result.append(currentLevel) return result ``` - Java代码示例（分层版，使用ArrayDeque）： ``` import java.util.*; 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 currentLevel = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); currentLevel.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } result.add(currentLevel); } return result; } ``` - 补充说明：TreeNode定义通常为： ``` class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } ```

Shopee推荐算法 日常实习一面 麻了

全站热榜

创作者周榜

Shopee推荐算法日常实习一面麻了