忍者算法

Appearance

从树的漫步到二叉树遍历：中序遍历的诗与智慧 ​

生活中的遍历启示 ​

想象你在一个迷人的森林里散步。森林里的每棵树都有自己独特的故事，而你的任务是以一种特定的方式依次聆听每棵树的声音。中序遍历就像是这样一次有序的森林漫步：先听左侧的树木，然后是当前所在的树，最后是右侧的树木。

遍历的本质 ​

二叉树的中序遍历（LeetCode第94题）遵循一个优雅的顺序：

  1. 先访问左子树
  2. 再访问根节点
  3. 最后访问右子树

这种方式特别适合有序二叉搜索树，因为它会按照升序输出节点值。

思路的进化之路 ​

第一站：递归的诗意 ​

递归是解决树遍历最自然的方式。就像讲一个故事：要了解整个故事，你需要先了解故事的左半部分，然后是核心情节，最后是右半部分。

java
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    traverse(root, result);
    return result;
}

private void traverse(TreeNode node, List<Integer> result) {
    // 递归的三个基本步骤
    if (node == null) return;
    
    // 1. 先访问左子树
    traverse(node.left, result);
    
    // 2. 访问当前节点
    result.add(node.val);
    
    // 3. 最后访问右子树
    traverse(node.right, result);
}

第二站：迭代的智慧 ​

递归虽然优雅，但对于深度较大的树可能导致栈溢出。迭代提供了一种显式管理"故事进度"的方式。

java
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new LinkedList<>();
    TreeNode current = root;
    
    while (current != null || !stack.isEmpty()) {
        // 1. 不断深入左子树
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        
        // 2. 访问栈顶节点
        current = stack.pop();
        result.add(current.val);
        
        // 3. 转向右子树
        current = current.right;
    }
    
    return result;
}

遍历的艺术与算法 ​

模式匹配 ​

让我们通过具体的树来理解遍历过程：

     4
   /   \
  2     6
 / \   / \
1   3 5   7

递归遍历顺序： 1 → 2 → 3 → 4 → 5 → 6 → 7

迭代遍历步骤：

  1. 压入1、2
  2. 弹出2，访问，压入3
  3. 弹出3
  4. 弹出4，访问
  5. 压入5、6 ... 如此类推

复杂度分析 ​

递归方法：

  • 时间复杂度：O(n)，每个节点访问一次
  • 空间复杂度：O(h)，h为树的高度（递归栈）
  • 优点：代码简洁，易于理解
  • 缺点：可能栈溢出

迭代方法：

  • 时间复杂度：O(n)
  • 空间复杂度：O(h)
  • 优点：显式控制遍历，避免递归栈溢出
  • 缺点：代码略显复杂

进阶思考 ​

  1. Morris遍历：O(1)空间复杂度的遍历方法
  2. 如何处理平衡与非平衡二叉树？
  3. 前序、中序、后序遍历的本质区别？

实际应用场景 ​

  • 二叉搜索树的排序
  • 表达式求值
  • 文件系统遍历
  • 编译器语法树分析

小结 ​

中序遍历教会我们：

  1. 递归思想的优雅
  2. 如何系统地遍历树形结构
  3. 迭代与递归的权衡
  4. 数据结构遍历的通用思维方式

记住：遍历树就像漫步在知识的森林，重要的是保持好奇和系统性！

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

🎯 回复【刷题清单】获取更多经典题目解析 👥 回复【加群】加入算法/面试交流群，一起学习进步 🧑‍💻 回复【代码】获取GitHub完整题解项目，包含Java/Python/JavaScript/Go/C++多语言实现

#算法面试 #LeetCode #数据结构