好的，我们这次来详细学习 LeetCode 第 94 题「二叉树的中序遍历」。

1. 题目描述

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

示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
解释：

    1
     \
      2
     /
    3

中序遍历顺序：左 → 根 → 右，所以是 1 的左子树为空，访问 1，然后访问 2 的左子树 3，再访问 2。

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

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

2. 理解中序遍历

中序遍历（Inorder Traversal）的访问顺序是：

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

对于二叉搜索树（BST），中序遍历的结果是 升序排列 的，但本题不要求是 BST，只是普通二叉树。

3. 递归解法（最直观）

递归的思路非常符合中序遍历的定义：

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

代码实现（Python）：

def inorderTraversal(root):
    result = []
    
    def inorder(node):
        if not node:
            return
        inorder(node.left)    # 左
        result.append(node.val) # 根
        inorder(node.right)   # 右
    
    inorder(root)
    return result

复杂度分析：

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

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

递归的本质是系统维护了一个调用栈，我们可以用 栈 来模拟这个过程。

迭代思路：

1. 从根节点开始，一直往左走，把经过的节点全部入栈（因为要先访问最左下的节点）。
2. 当走到最左边（当前节点为 None）时，从栈中弹出节点，这个节点就是当前要访问的节点，加入结果。
3. 然后转向该节点的右子树，重复步骤 1。

逐步模拟（示例 1 [1,null,2,3]）：

• 初始：curr = 1，栈 []，结果 []
• 循环 1：curr=1 入栈，curr=1.left → None
• 循环 2：弹出栈顶 1，结果 [1]，curr=1.right=2
• 循环 3：curr=2 入栈，curr=2.left=3
• 循环 4：curr=3 入栈，curr=3.left → None
• 循环 5：弹出栈顶 3，结果 [1,3]，curr=3.right → None
• 循环 6：弹出栈顶 2，结果 [1,3,2]，curr=2.right → None
• 结束。

迭代代码：

def inorderTraversal(root):
    stack = []
    result = []
    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

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(h)，h 为树高

5. Morris 中序遍历（O(1) 空间）

如果想用 O(1) 额外空间（不含结果数组）完成，可以用 Morris 遍历。
它的核心思想是利用树的空闲指针（叶子节点的空指针）来记录回溯路径。

Morris 步骤：

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

Morris 代码：

def inorderTraversal(root):
    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(n)
• 空间 O(1)

6. 总结

• 递归：最直观，容易写，但空间 O(h)。
• 迭代：显式栈模拟递归，适合面试展示对遍历过程的理解。
• Morris：O(1) 空间，但会修改树结构（最后恢复），适合对空间要求极高的场景。

这三种方法希望你都能掌握，特别是迭代法，因为很多树相关题目的非递归写法都基于这种栈的思路。