忍者算法

Appearance

层序遍历：树的呼吸与流动 ​

从生活看遍历：层与层的对话 ​

想象一个社交派对。人们不是随机交谈，而是按楼层、按桌次有序互动。二叉树的层序遍历，正如这样一场有组织的社交盛宴，每一层都有自己独特的节奏和故事。

层序遍历的本质 ​

层序遍历（LeetCode第102题）的核心：

  • 自上而下，从根开始
  • 同一层的节点依次访问
  • 先进先出的队列管理

递归解法：有序的层次之旅 ​

java
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    
    // 辅助递归方法
    traverseLevel(root, 0, result);
    
    return result;
}

private void traverseLevel(TreeNode node, int level, List<List<Integer>> result) {
    // 遇到空节点直接返回
    if (node == null) return;
    
    // 如果当前层还没有列表，创建新列表
    if (level >= result.size()) {
        result.add(new ArrayList<>());
    }
    
    // 将当前节点加入对应层
    result.get(level).add(node.val);
    
    // 递归遍历左右子树，层级+1
    traverseLevel(node.left, level + 1, result);
    traverseLevel(node.right, level + 1, result);
}

迭代解法：队列的精确编排 ​

java
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    
    if (root == null) return result;
    
    // 队列管理节点遍历
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        // 记录当前层的节点数
        int levelSize = queue.size();
        List<Integer> 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;
}

性能分析 ​

时间复杂度：O(n) ​

  • 每个节点访问一次
  • 节点数量决定遍历时间

空间复杂度：O(w) ​

  • w为树的最大宽度
  • 队列空间消耗
  • 最坏情况可能接近O(n/2)

思考与拓展 ​

  1. 为什么队列适合层序遍历？
  2. 如何处理特殊二叉树？
  3. 还有哪些遍历方式？

应用场景 ​

  • 网络拓扑分析
  • 组织结构层级展示
  • 状态机的层次遍历
  • 图形用户界面的渲染

遍历的启示 ​

层序遍历教会我们：

  • 有序胜于随机
  • 系统性思考的重要性
  • 复杂问题可以通过简单规则解决

记住，遍历树就像理解一个复杂系统，重要的是保持结构性思维！

作者：忍者算法 公众号：忍者算法

我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～