LC94　二叉树的中序遍历¶

简单通过率 78.3%python3核心代码模式二叉树样例通过牛客 AC栈树深度优先搜索二叉树

牛客原题　源码

讲解章节：树的基础与遍历

一句话

显式栈模拟「左根右」，一路向左压栈，弹出即访问。

解题思路¶

这题考什么¶

中序（inorder）的定义是「左子树 -> 根 -> 右子树」，写成递归只要三行。题目的进阶问的却是迭代版，考的正是把递归的调用栈搬到手里自己管。

递归之所以能工作，是因为它在下钻左子树之前，把「还没访问的根」和「还没走的右子树」留在了调用栈上。手写迭代要复现的就是这件事：

cur 沿 left 指针一路下钻，沿途每个节点都压栈（它们自己和右子树都欠着）；
走到头就弹出栈顶 —— 这个节点的左子树已经全部访问完，轮到它自己；
访问完把 cur 转向它的右孩子，右子树重复同样的过程。

栈里存的是「左子树尚未处理完的祖先链」，自底向上正好是当前位置到根的路径，元素个数不超过树高。三种遍历的迭代模板见树的基础与遍历的「二叉树的三种遍历」一节。

示例 1 的 [1,null,2,3]：根是 1，1 没有左孩子、右孩子是 2，2 的左孩子是 3。

cur=1 压栈 [1]，1 无左孩子 -> 弹 1，记 1，cur 转到右孩子 2
cur=2 压栈 [2]，转到左孩子 3 压栈 [2,3]，3 无左孩子
弹 3，记 3，转到 3 的右孩子（空）
弹 2，记 2，转到 2 的右孩子（空）；栈空且 cur 空，结束

访问序列 1, 3, 2，与样例输出一致。

数据规模与复杂度¶

节点数在 [0, 100]，节点值在 [-100, 100]。每个节点恰好入栈一次、出栈一次，时间 O(n)；空间 O(h)，h 为树高，链状树退化到 O(n)，本题也就 100。这个量级递归同样跑得动（深度最多 100，低于 CPython 默认的 1000 层上限），选迭代一是题目的进阶就在问它，二是给同专题里 n 到 1e4 的 LC98、LC230 打底。

坑在哪¶

外层循环条件必须是「cur 非空或栈非空」，两个条件缺一不可。只写 while stack，起始栈是空的，循环一次都进不去；只写 while cur，弹出一个叶子后 cur 变成 None，还压在栈里的祖先再也没有机会被访问。
访问时机是弹出时，不是压栈时。压栈发生在下钻左子树之前，那时该节点的左子树一个都没访问过，此刻记值得到的是前序而不是中序。
空树要返回空列表。这份写法天然满足：cur 一开始就是 None、栈也是空的，两个循环条件同时不成立，直接落到 return out。题面示例 2 给的正是空树。
判空统一写 is not None，不写 if node.left。TreeNode 没有定义真值语义，两种写法此刻等价，但显式判空才不会在别的题上被自定义类型绊倒。

参考实现¶

solutions/leetcode/LC94/sol.py
from typing import List, Optional


class Solution:
    def inorderTraversal(self, root: "Optional[TreeNode]") -> List[int]:
        out: List[int] = []
        # 栈里是「左子树还没处理完」的祖先链，自底向上就是当前位置到根的路径
        stack: List["TreeNode"] = []
        cur = root
        # 两个条件缺一不可：cur 非空是起步与「刚转到右子树」的状态，
        # cur 为空而栈非空是「左边走到头，该回头访问祖先」的状态
        while cur is not None or stack:
            # 一路向左下钻，沿途节点欠着「自己」和「右子树」，先记在栈上
            while cur is not None:
                stack.append(cur)
                cur = cur.left
            # 弹出的节点左子树已经全部访问完，此刻轮到它 —— 这就是中序里的「根」
            node = stack.pop()
            out.append(node.val)
            # 转向右子树，下一轮外层循环会把右子树的最左链继续压栈
            cur = node.right
        return out

LC94 二叉树的中序遍历¶