BM24　二叉树的中序遍历¶

中等通过率 59.23%python3核心代码模式样例通过牛客 AC树递归广度优先搜索(BFS)dfs

一句话

一路向左压栈，弹出时访问，再转向右子树。

解题思路¶

这题考什么¶

中序（inorder）的定义是「左子树 -> 根 -> 右子树」：一个节点要等它的整棵左子树访问完才轮到自己。前序可以「弹出即访问」，中序不行—— 根被看到的时刻远早于该访问它的时刻，所以栈的角色变了：它存的是「已经路过、但左子树还没处理完，因此欠着一次访问」的祖先链。

循环写成两层：

内层沿左指针一路下探，把「当前节点、它的左孩子、左孩子的左孩子……」整条路径压进栈，直到走到 None；此刻栈顶是这一段的最左端节点。
外层弹出栈顶：它能被弹出，说明左子树已经全部处理完，此刻访问它，然后把游标换成它的右孩子，回到内层——右子树按同样规则展开。

示例 1 的 {1,2,#,#,3}：根 1，1 的左孩子是 2，2 的右孩子是 3。 cur=1 -> 压 1、压 2，走到 None 栈 [1, 2] 弹 2，访问 2，cur = 2 的右孩子 3 栈 [1] 压 3，走到 None；弹 3，访问 3 栈 [1] 弹 1，访问 1 栈 [] 访问序列 2, 3, 1，与样例输出一致。

这套「一路向左」模板见树的基础与遍历的「二叉树的三种遍历」一节。

数据规模与复杂度¶

题面正文写 0 <= n <= 1000、|val| <= 1000，「备注」一栏另写了 n <= 100、 |val| <= 100 两套不一致的上界；按宽的那套准备即可。时限「其他语言 2 秒」。每个节点恰好入栈一次、出栈一次，时间 O(n)；空间 O(h)，h 为树高，链状树退化到 O(n)，即栈里一次能压满 1000 个节点。

坑在哪¶

外层循环条件必须是「栈非空或游标非空」两者取或。只判栈非空，第一轮栈还是空的，函数直接返回 []；只判游标非空，弹出根之后若右子树为空就停了，上层祖先永远回溯不到。
访问一个节点后必须把游标改成它的右孩子，而不是置回 None。置 None 会让整棵右子树被跳过，示例 4 的 {1,#,2} 会只输出 [1]。
空树按题面是合法输入（示例 2 直接给 {}，期望 []）。这份写法不需要额外的空树分支：root 为 None 时两个循环条件同时不成立，天然返回 []。
写成递归有实际风险：n 可以取到 1000，而 CPython 的默认递归上限正是 1000 层，链状树（每个节点只有左孩子）的递归深度就是 n，加上判题驱动本身占掉的几层，足以抛 RecursionError。调大计数器也救不了 C 栈，三层限制见 DFS 深度优先搜索的 60.4 节。

参考实现¶

solutions/nowcoder/BM24/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
        # 两个条件缺一不可：栈空但游标还在（刚进入右子树）也得继续
        while stack or cur is not None:
            # 内层不变量：压进去的恰好是从 cur 到它最左端后代的整条路径
            while cur is not None:
                stack.append(cur)         # 把到最左端的整条路径压进去
                cur = cur.left
            cur = stack.pop()             # 弹出的点，其左子树已访问完
            out.append(cur.val)
            cur = cur.right               # 根访问完，转去右子树
        return out

BM24 二叉树的中序遍历¶