中序遍历（Inorder Traversal） 是二叉树三种基本深度优先遍历方式之一（另外两种是前序、后序）。它的核心规则非常简单：

先遍历左子树 → 再访问根节点 → 最后遍历右子树
（简称：左 - 根 - 右）

---

🌳 通俗理解

想象你站在二叉树的根节点，要按顺序“拜访”所有节点：

1. 先一头扎进左子树，用同样的规则（左→根→右）遍历它；
2. 等左子树全部拜访完，才回到当前根节点并记录它；
3. 最后去拜访右子树，同样用（左→根→右）的规则。

这个过程天然具有递归性质——每个子树都是一个更小的二叉树，处理逻辑完全相同。

---

📌 关键特性

• 对二叉搜索树（BST）有特殊意义：
  中序遍历 BST 的结果一定是升序序列（因为 BST 性质：左子树 < 根 < 右子树）。
• 时间复杂度：O(n)（每个节点访问一次）
  空间复杂度：O(h)（h 为树高，递归栈或显式栈的深度）。

---

🌰 举例说明

        A
       / \
      B   C
     / \   \
    D   E   F

中序遍历步骤：

1. 从根 A 开始，先遍历左子树（以 B 为根）
   • 遍历 B 的左子树（D）→ 访问 D
   • 访问 B
   • 遍历 B 的右子树（E）→ 访问 E
2. 访问根 A
3. 遍历右子树（以 C 为根）
   • 访问 C（C 无左子树）
   • 遍历 C 的右子树（F）→ 访问 F

结果：[D, B, E, A, C, F]

---

💡 为什么叫“中序”？

• “中”指根节点在遍历顺序的中间位置（左子树之后，右子树之前）。
• 对比其他遍历：
  • 前序：根 → 左 → 右（根在前）
  • 后序：左 → 右 → 根（根在后）

---

🛠 实现方式

方法 1：递归（最直观）

def inorderTraversal(root):
    if not root:
        return []
    return (inorderTraversal(root.left) + 
            [root.val] + 
            inorderTraversal(root.right))

方法 2：迭代（用栈模拟递归）

def inorderTraversal(root):
    result, stack, current = [], [], root
    while current or stack:
        # 一路向左，将路径节点入栈
        while current:
            stack.append(current)
            current = current.left
        # 弹出栈顶（最左节点），访问它
        current = stack.pop()
        result.append(current.val)
        # 转向右子树
        current = current.right
    return result

---

✅ 总结

表格

遍历类型	顺序	应用场景
中序	左 → 根 → 右	BST 升序输出、表达式树求值
前序	根 → 左 → 右	复制树、序列化
后序	左 → 右 → 根	删除树、计算目录大小

中序遍历的本质是深度优先探索左分支，回溯时处理根，再探索右分支，这种“分治”思想是树算法的基础。