问题说明（含示例）

问题描述：给定二叉树的根节点 root，返回该二叉树的中序遍历结果。

中序遍历定义：遍历顺序遵循「左子树 → 根节点 → 右子树」的规则（即 “左 - 根 - 右”），是二叉树三种基础遍历（前序、中序、后序）之一，需递归或迭代实现。

示例：

1. 输入：root = [1,null,2,3]（二叉树结构：根为 1，无左子树；右子树为 2，2 的左子树为 3，无右子树）输出：[1,3,2]解释：

   • 遍历 1 的左子树：为空，无节点；
   • 访问根节点 1，加入结果；
   • 遍历 1 的右子树（节点 2）：
     • 遍历 2 的左子树（节点 3）：左子树为空 → 访问 3 → 右子树为空；
     • 访问根节点 2 → 遍历 2 的右子树：为空；最终结果为 [1,3,2]。

2. 输入：root = []（空树，无任何节点）输出：[]解释：无节点可遍历，返回空列表。

3. 输入：root = [1]（仅含根节点的树）输出：[1]解释：遍历 1 的左子树（空）→ 访问 1 → 遍历 1 的右子树（空），结果为 [1]。

解题关键

中序遍历的核心是遵循「左 - 根 - 右」顺序，主流实现方式有递归法和迭代法，两种方法的时间复杂度均为 O(n)（n 为节点数，每个节点访问一次），空间复杂度均为 O(n)（递归用栈帧，迭代用显式栈）。

1. 递归法核心思路

• 终止条件：当前节点为 null（子树为空，无需遍历）；
• 递归逻辑：
  1. 先递归遍历当前节点的左子树；
  2. 访问当前节点（将节点值加入结果列表）；
  3. 再递归遍历当前节点的右子树。

2. 迭代法核心思路（模拟递归栈）

• 用栈（Stack） 存储待处理的节点，利用栈 “先进后出（LIFO）” 特性模拟递归的 “左子树优先” 逻辑；
• 步骤：
  1. 初始化指针 cur 指向根节点，结果列表 res 为空；
  2. 循环：若 cur 不为空或栈不为空：
     • 先将 cur 及其所有左子树节点依次压入栈（确保左子树优先处理）；
     • 弹出栈顶节点，访问该节点（加入 res）；
     • 将 cur 指向弹出节点的右子树（处理右子树）。

对应代码

方法 1：递归法（简洁直观）

from typing import Optional, List

# 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]:
        res = []  # 存储遍历结果
        
        # 定义递归辅助函数
        def dfs(node):
            if not node:  # 终止条件：节点为空，返回
                return
            dfs(node.left)  # 1. 递归遍历左子树
            res.append(node.val)  # 2. 访问根节点，加入结果
            dfs(node.right)  # 3. 递归遍历右子树
        
        dfs(root)  # 从根节点开始递归
        return res

1）递归的本质：“大问题拆成小问题，小问题解法相同”

中序遍历的核心需求是 “遍历整棵树”，但这个 “大问题” 可以拆成 3 个小问题：

• 遍历当前节点的左子树（小问题 1）；
• 访问当前节点（核心操作）；
• 遍历当前节点的右子树（小问题 2）。

而 “遍历左子树” 这个小问题，和 “遍历整棵树” 的解法完全一样 —— 依然要遵循 “左 - 根 - 右” 的顺序。所以我们可以直接用 dfs(node.left) 调用同一个函数来处理左子树，同理用 dfs(node.right) 处理右子树。

比如示例 1 中的树 1→2→3（1 的右是 2，2 的左是 3）：

• 调用 dfs(1)（处理整棵树）→ 先调用 dfs(1.left)（1 的左是空，终止）；
• 访问 1 后，调用 dfs(1.right=2)（处理 2 的子树）→ 先调用 dfs(2.left=3)（处理 3 的子树）；
• 调用 dfs(3) → 先调用 dfs(3.left)（空，终止）→ 访问 3 → 调用 dfs(3.right)（空，终止）；
• 回到 dfs(2) → 访问 2 → 调用 dfs(2.right)（空，终止）；
• 最终完成所有遍历。

2）终止条件：避免 “无限递归”

递归能正常运行的关键是必须有终止条件—— 当子问题小到 “无需继续拆分” 时，直接返回，不再调用自身。

代码中的 if not node: return 就是终止条件：

• 当 node 是 null（比如叶子节点的左 / 右子树），说明 “这个子树为空，没有节点可遍历”，此时直接返回，不会再调用 dfs(node.left) 或 dfs(node.right)；
• 没有这个条件的话，函数会一直调用 dfs(null.left) → dfs(null.left) → ... 无限循环，最终导致 “栈溢出” 错误（Python 会报 RecursionError）。

3）Python 的 “函数调用栈” 支持递归

Python 内部用 “函数调用栈”（一种 “先进后出” 的结构）来管理递归调用，每次调用函数时，都会把当前函数的 “状态”（比如 node 的值、当前执行到哪一行代码）压入栈中；当函数遇到 return 时，再从栈中弹出之前的状态，回到上一层函数继续执行。

比如调用 dfs(1) 后，流程在 “调用 dfs(1.left)” 处暂停，把 dfs(1) 的状态压入栈；等 dfs(1.left) 执行完（返回），再从栈中取出 dfs(1) 的状态，继续执行 “访问 1” 和 “调用 dfs(1.right)”—— 这就是递归能 “回溯” 的原因。

简单说：dfs 能调用自身，是因为 “遍历子树” 和 “遍历整棵树” 的逻辑完全一样，且有终止条件防止无限循环，再加上 Python 的调用栈帮我们管理回溯，最终能高效完成二叉树的遍历。

4）用递归执行流程理解：先 “钻到底” 左子树，再回退记录根

递归的特点是 “先深入，后回退”，dfs(node.left) 会优先执行到最底层的左子节点，直到触发终止条件（node == null），才会 “回退” 到上一层节点执行 res.append(...)。

以示例 1 的树 1→2→3（1 的右是 2，2 的左是 3）为例，具体流程如下：

1. 调用 dfs(1) → 先执行 dfs(1.left)（1 的左是空，直接返回）；
2. 回退到 dfs(1)，执行 res.append(1) → 结果列表变成 [1]；
3. 再执行 dfs(1.right=2) → 进入 dfs(2)，先执行 dfs(2.left=3)；
4. 进入 dfs(3)，先执行 dfs(3.left)（3 的左是空，返回）；
5. 回退到 dfs(3)，执行 res.append(3) → 结果列表变成 [1,3]；
6. 再执行 dfs(3.right)（3 的右是空，返回）；
7. 回退到 dfs(2)，执行 res.append(2) → 结果列表变成 [1,3,2]；
8. 再执行 dfs(2.right)（2 的右是空，返回）；
9. 最终返回 [1,3,2]，完全符合中序要求。

方法 2：迭代法（显式栈模拟）

from typing import Optional, List

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]:
        res = []  # 存储遍历结果
        stack = []  # 显式栈，存储待处理节点
        cur = root  # 指针，用于遍历左子树
        
        while cur or stack:
            # 步骤1：将当前节点及其所有左子树节点压入栈
            while cur:
                stack.append(cur)
                cur = cur.left  # 左子树优先，一直往左走
            # 步骤2：弹出栈顶节点（左子树处理完），访问该节点
            node = stack.pop()
            res.append(node.val)
            # 步骤3：处理弹出节点的右子树
            cur = node.right
        
        return res

对应的基础知识

实现中序遍历需掌握以下基础概念与操作：

1. 二叉树节点结构

• TreeNode 类包含三个属性：val（节点值）、left（指向左子节点的指针，默认 None）、right（指向右子节点的指针，默认 None）；
• 二叉树的遍历依赖 left 和 right 指针，无法像数组一样通过索引直接访问，需按 “左 - 根 - 右” 顺序递归或迭代跳转。

2. 递归函数的核心要素

• 终止条件：if not node（当节点为空时，无需继续递归，避免无限调用）；
• 递归调用：函数 dfs(node) 自身调用 dfs(node.left) 和 dfs(node.right)，将大问题（遍历整棵树）拆分为小问题（遍历左 / 右子树）。

3. 栈的基础操作

• 迭代法中用列表模拟栈：stack.append(node) 对应 “压栈”，stack.pop() 对应 “弹栈”（默认弹出列表最后一个元素，符合栈的 LIFO 特性）；
• 栈的作用是 “暂存待处理的根节点”：先处理左子树，再通过栈取出根节点，最后处理右子树。

4. 列表与 Optional 类型

• 列表 res 用 append() 方法存储遍历结果，最终返回该列表；
• Optional[TreeNode] 表示 root 可能是 TreeNode 实例（非空树），也可能是 None（空树），符合 Python 类型提示规范，避免空指针错误。

对应的进阶知识

中序遍历的实现涉及二叉树遍历的深层逻辑与复杂度分析：

1. 递归的栈帧原理

• 递归法虽代码简洁，但本质依赖 “函数调用栈”（系统隐式维护的栈帧）：每次调用 dfs(node.left) 时，当前函数状态（如 node 的地址）会被压入栈帧；当 node 为空时，栈帧弹出，回到上一层函数继续执行 “访问根节点” 和 “遍历右子树”；
• 递归的空间复杂度 O(n) 源于栈帧数量：最坏情况下（树为左斜树，所有节点只有左子树），栈帧数量等于节点数 n。

2. 迭代法与递归的等价性

• 迭代法用 “显式栈” 模拟了递归的 “隐式栈帧”：栈中存储的节点，本质是递归中需要 “回溯访问” 的根节点；
• 对比：递归的 “压栈” 是系统自动完成（栈帧），迭代的 “压栈” 是手动 stack.append(node)；递归的 “弹栈” 是系统自动（函数返回），迭代的 “弹栈” 是手动 stack.pop()。

3. 中序遍历的应用场景

• 中序遍历的核心价值体现在二叉搜索树（BST） 中：BST 的中序遍历结果是严格升序序列（左子树值 < 根节点值 < 右子树值）；
• 应用：可通过中序遍历判断一棵树是否为 BST，或从 BST 中获取升序元素列表、查找第 k 小元素等。

4. 复杂度分析

• 时间复杂度：O(n)，无论递归还是迭代，每个节点都会被 “访问一次”（加入结果列表）和 “处理两次”（压栈和弹栈），总操作次数与节点数成正比；
• 空间复杂度：O(n)，最坏情况（左斜树或右斜树）下，栈中需存储所有 n 个节点；最好情况（完全二叉树）下，栈中存储 log n 个节点（树的高度）。