好的，我们来学习 LeetCode 第 94 题：二叉树的中序遍历 (Binary Tree Inorder Traversal)。

这道题是学习二叉树遍历的基石，理解它对于掌握树结构至关重要。我会从最基本的概念开始，循序渐进地带你掌握它。

1. 题目描述

题目链接：https://leetcode.com/problems/binary-tree-inorder-traversal/

题目要求：
给定一个二叉树的根节点 root ，返回它的 中序遍历 的结果。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

图示：

    1
     \
      2
     /
    3

先访问左子树（节点 2 的左子树是 3），然后根节点 2，所以顺序是 1（1 的左子树为空，访问 1 本身）→ 然后右子树 2 的左子树 3 → 3 → 2。

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

进阶：递归算法很简单，你可以使用迭代算法完成吗？

2. 核心概念：二叉树的中序遍历

中序遍历是二叉树的一种深度优先遍历方式，顺序为：

1. 遍历左子树
2. 访问根节点
3. 遍历右子树

记忆口诀：左根右。

举例：

    A
   / \
  B   C

中序遍历：B → A → C。

3. 递归解法（最直观的方法）

递归思路完全按照定义：

1. 如果当前节点为空，直接返回。
2. 先递归遍历左子树。
3. 访问当前节点（将节点值加入结果列表）。
4. 再递归遍历右子树。

代码实现（Python）：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        
        def inorder(node):
            if node is None:
                return
            inorder(node.left)   # 左
            result.append(node.val)  # 根
            inorder(node.right)  # 右
            
        inorder(root)
        return result

时间复杂度：O(n)，每个节点访问一次。
空间复杂度：O(h)，其中 h 是树的高度，递归调用栈的深度。

4. 迭代解法（使用显式栈）

递归本质是系统栈，我们可以用显式栈模拟递归过程。

迭代思路：

1. 从根节点开始，把所有左子节点依次入栈，直到最左边的叶子节点。
2. 弹出栈顶节点（这是当前最左节点），访问它。
3. 转向该节点的右子树，重复步骤 1。

这个过程模拟了递归的“深入左子树 → 回溯根节点 → 深入右子树”。

步骤演示（示例 1：root = [1,null,2,3]）：

• 初始：curr = 1，栈空。
• 节点 1 的左子为空，所以没有一直向左入栈的过程，直接进入循环后半部分。
• 但更通用的写法是循环条件为 while curr or stack，我们按标准迭代中序遍历步骤来：

迭代代码：

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        stack = []
        curr = root
        
        while curr or stack:
            # 深入左子树
            while curr:
                stack.append(curr)
                curr = curr.left
            # 当前节点为空，说明左走到头，回溯
            curr = stack.pop()
            result.append(curr.val)  # 访问根节点
            # 转向右子树
            curr = curr.right
            
        return result

执行流程示例（示例 1）：

1. curr = 1，入栈 [1]，curr = 1.left = None。
2. 弹出栈顶 1，result = [1]，curr = 1.right = 2。
3. curr = 2 非空，入栈 [2]，curr = 2.left = 3。
4. curr = 3 非空，入栈 [2, 3]，curr = 3.left = None。
5. 弹出 3，result = [1, 3]，curr = 3.right = None。
6. 弹出 2，result = [1, 3, 2]，curr = 2.right = None。
7. 结束。

5. 莫里斯遍历（Morris Traversal，O(1) 空间）

莫里斯遍历利用叶子节点的空右指针指向中序遍历的后继节点，从而避免使用栈。

算法步骤：

1. 初始化 curr 为根节点。
2. 当 curr 不为空：
   • 如果 curr 没有左子树：
     • 访问 curr
     • curr = curr.right
   • 否则：
     • 找到 curr 左子树的最右节点（即中序遍历下 curr 的前驱节点）
     • 如果最右节点的右指针为空：
       • 将其右指针指向 curr（建立回环）
       • curr = curr.left
     • 如果最右节点的右指针为 curr（说明左子树已遍历完）：
       • 恢复最右节点的右指针为 None
       • 访问 curr
       • curr = curr.right

代码：

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        curr = root
        
        while curr:
            if curr.left is None:
                result.append(curr.val)
                curr = curr.right
            else:
                # 找前驱节点
                pre = curr.left
                while pre.right and pre.right != curr:
                    pre = pre.right
                if pre.right is None:
                    pre.right = curr  # 建立回环
                    curr = curr.left
                else:
                    pre.right = None  # 断开回环
                    result.append(curr.val)
                    curr = curr.right
                    
        return result

优点：空间复杂度 O(1)（除了输出列表）。
缺点：修改了树结构（最后会恢复）。

6. 总结

关键点：

• 中序遍历顺序：左 → 根 → 右。
• 递归是基础，必须掌握。
• 迭代法用栈模拟递归，是面试常见考点。
• 莫里斯遍历是进阶优化，体现对遍历过程的深刻理解。

理解了这些，你就掌握了二叉树中序遍历的所有常见解法！