- 正确答案：层序遍历（Level Order Traversal）是按树的每一层从左到右访问节点的一种遍历方式，通常使用队列实现。所谓“层序遍历改”，在校园招聘面试中通常指对标准层序遍历进行变式，例如：按层输出每层节点、Z字形（锯齿形）遍历、逆层序输出、每层反转等。最常见的“改”是“Z字形层序遍历”或“按层返回结果”。以下以“Z字形层序遍历”为例给出完整解答： - 解答思路： 1. 标准层序遍历使用队列，逐层处理节点。 2. Z字形要求奇数层从左到右，偶数层从右到左（或相反），因此需要记录当前层数，并根据层数决定是否反转该层结果。 3. 使用队列进行广度优先搜索（BFS），同时用一个变量 level 记录当前层数（从0或1开始），每处理完一层，level++。 4. 对于需要反向输出的层，将该层结果反转后再加入最终结果列表。 - 深度知识讲解：层序遍历本质上是图的广度优先搜索（BFS）在二叉树上的应用。其核心数据结构是队列（FIFO），保证先进入队列的节点先被处理，从而实现从上到下、从左到右的顺序。二叉树节点定义如下（常见形式）： ``` class TreeNode: int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } ``` 队列可以使用语言内置结构，如 Java 的 LinkedList 或 Python 的 deque。在Z字形遍历中，关键点是“按层分割”。由于队列是连续存储的，必须通过记录每层的节点数量来区分层边界。方法是在每一层开始前获取当前队列大小 size，表示该层的节点数，然后只处理这 size 个节点。时间复杂度：O(n)，每个节点访问一次。空间复杂度：O(w)，w 是树的最大宽度，即队列最多存储一层的所有节点。进阶考点可能包括： - 不使用队列实现层序遍历？（不可行，除非用DFS模拟，但本质不同） - 如何用DFS实现Z字形输出？可以用递归，按深度存储节点，最后对偶数层反转。 - 层序遍历能否用于N叉树？可以，只需将左右子节点扩展为 children 列表。 - 代码示例（Z字形层序遍历，Java风格伪代码）： ``` public List> zigzagLevelOrder(TreeNode root) { List> result = new ArrayList<>(); if (root == null) return result; Queue queue = new LinkedList<>(); queue.offer(root); int level = 0; while (!queue.isEmpty()) { int size = queue.size(); List currentLevel = new ArrayList<>(); for (int i = 0; i < size; 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); } } // 奇数层反转（假设根为第0层，从左到右；第1层从右到左） if (level % 2 == 1) { Collections.reverse(currentLevel); } result.add(currentLevel); level++; } return result; } ``` - 扩展知识点： 1. 变体1：仅输出最后一层节点，从右到左。 - 方法：正常层序遍历，记录每层，最后取最后一层并反转。 2. 变体2：之字形打印，但先从右到左。 - 调整 level 初始判断条件即可。 3. 变体3：按层输出，但每层内部按降序排序。 - 不再是遍历问题，而是每层收集后排序，需注意与Z字形区别。 4. 变体4：层序遍历重建二叉树。 - 给定层序数组，构造完全二叉树，可用索引关系：i 的左孩子是 2i+1，右孩子是 2i+2。 - 底层原理强调：队列的使用确保了广度优先的顺序。在多叉树或图中，BFS均依赖队列避免深度优先。而“分层处理”的技巧——每次只处理当前队列长度个节点——是解决所有层相关变种的核心模式。 - 总结： “手撕层序遍历改”重点考察： 1. 是否掌握BFS基本框架； 2. 是否能控制层边界（size技巧）； 3. 是否理解双向输出逻辑（反转或双端队列）； 4. 编码细节：空树处理、null判断、集合操作。建议练习多种变体，如：反向层序（从下到上）、每层平均值、层的最大值、找最左节点等，均基于同一模板修改。

快手商业化广告客户端二面

全站热榜

创作者周榜