LeetCode 94. 二叉树的中序遍历｜Python 解法详解

CSDN 算法专题 · 二叉树 | 难度：简单

题目信息

• 题号：94
• 难度：简单
• LeetCode：题目链接

题目描述

给定二叉树根节点，返回节点值的中序遍历序列。中序顺序为左子树、根节点、右子树。

示例

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

约束

节点数不超过 100；节点值为整数。

解题思路

核心观察

递归函数负责遍历一棵子树：空节点直接返回，依次递归左子树、记录根值、递归右子树。顺序本身就是算法定义。

推导与执行步骤

1. 创建结果列表
2. 递归访问左子树
3. 记录当前节点值
4. 递归访问右子树

为什么这个方法正确

算法始终围绕上述核心观察维护有效状态，并且每一步只排除已经能够证明不可能产生更优答案的情况。按照执行步骤处理后，所有可能影响答案的元素或节点都会被恰好检查，因此不会遗漏合法答案；状态更新又严格遵守题目约束，所以最终结果有效。

从边界看，空区间、单个元素、全部相同或完全不匹配等情况都会落入初始化条件或循环终止条件，不需要依赖未定义状态。实现时再重点检查下标、空节点和重复元素，即可保证算法在极端输入下仍然成立。

Python 代码

# 解法核心：递归函数负责遍历一棵子树：空节点直接返回，依次递归左子树、记录根值、递归右子树。顺序本身就是算法定义。
# 实现步骤：
# 1. 创建结果列表
# 2. 递归访问左子树
# 3. 记录当前节点值
# 4. 递归访问右子树

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 = []  # 保存遍历过程中得到的结果
        self.inorder(root, res)
        return res

    def inorder(self, root, res):
        if not root:
            return
        self.inorder(root.left, res)
        res.append(root.val)
        self.inorder(root.right, res)

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(h)

易错点

记录根节点的位置必须在左右递归之间。

总结

这道题的关键是：递归函数负责遍历一棵子树：空节点直接返回，依次递归左子树、记录根值、递归右子树。理解这一点后，再结合边界条件检查，代码就能保持清晰且稳定。