BM23　二叉树的前序遍历¶

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

牛客原题　源码

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

一句话

显式栈模拟「根左右」，压栈时先右后左。

解题思路¶

这题考什么¶

前序（preorder）的定义是「根 -> 左子树 -> 右子树」，写成递归只要三行。真正要练的是把递归改写成显式栈：栈是后进先出，只要坚持「弹出即访问、压栈时先压右孩子后压左孩子」，出栈顺序就恰好是前序。

为什么这个顺序成立：根一入栈就立刻被弹出，所以根最先；左孩子压在右孩子上面，下一轮先出，而左孩子的整棵子树又会在它被弹出后立刻铺满栈顶，于是左子树的全部节点都排在右孩子之前。

示例 1 的 {1,#,2,3}：根是 1，1 没有左孩子、右孩子是 2，2 的左孩子是 3。
栈的演变（栈顶写在右端）：
    [1] -> 弹 1，压右孩子 2      -> [2]
    [2] -> 弹 2，压左孩子 3      -> [3]
    [3] -> 弹 3                  -> []
访问序列 1, 2, 3，与样例输出一致。

栈里存的是「已经确定要访问、但还没轮到」的节点，任一时刻它们构成若干条尚未展开的分支，元素个数不超过树高。三种遍历的迭代模板见树的基础与遍历的「二叉树的三种遍历」一节。

数据规模与复杂度¶

n <= 100，节点值在 [1, 100] 且互不相同；时限「其他语言 2 秒」。每个节点恰好入栈一次、出栈一次，时间 O(n)；空间 O(h)，h 为树高，链状树退化到 O(n)。这个量级怎么写都够，选迭代是为了跟本专题统一口径：同一批的 BM28、BM38 的 n 到 1e5，那里递归版是必须改写的。

坑在哪¶

压栈顺序必须先右后左。写反了出栈顺序变成「根右左」，整个序列错位——那个镜像序列另有用处，BM25 的后序解法正是把它整体逆序。
访问时机必须是弹出时，不是压栈时。若改成「压栈就记值」，右孩子会先于左孩子被记录，第二层往后全乱。
if root is None 这道防线不能省。少了它 stack 会被塞进一个 None，下一轮 node.val 直接 AttributeError。题面写 n >= 1，但题面的边界描述从来不是担保，同专题 BM24 的示例 2 就直接给了空树 {}。
判空写 is not None 而不是 if node.left。TreeNode 没有定义真值语义，这两种写法此刻等价，但统一成显式判空才不会在别的题上被自定义类型绊倒。

参考实现¶

solutions/nowcoder/BM23/sol.py
from typing import List, Optional


class Solution:
    def preorderTraversal(self, root: "Optional[TreeNode]") -> List[int]:
        # 空树返回空列表；这一句同时挡住了下面「栈里必然是真节点」的前提
        if root is None:
            return []
        out: List[int] = []
        # 循环不变量：栈里全是「已确定要访问、尚未轮到」的非空节点
        stack = [root]
        while stack:
            node = stack.pop()
            out.append(node.val)          # 弹出即访问 -> 根最先
            # 后进先出，所以压栈顺序与访问顺序相反：右先压、左后压
            if node.right is not None:
                stack.append(node.right)  # 右先压，压得深，后出
            if node.left is not None:
                stack.append(node.left)   # 左后压，压在顶上，先出
        return out

BM23 二叉树的前序遍历¶