LeetCode 144. 二叉树的前序遍历

◎

本节目标

用显式栈按根、左、右顺序访问二叉树。

这道题是遍历与层序视角中“进入节点即处理”的最小母题。题目给出二叉树根节点；空树的结果是空序列。

查看 LeetCode 原题

朴素思路与瓶颈

递归写法会自然地先处理根，再递归左右子树，但调用栈隐藏了待处理节点的顺序。这里直接把这部分工作显式写成栈，避免依赖递归。

核心不变量

栈中每个节点都尚未被访问，栈顶是下一次应访问的节点。弹出一个节点后先压右孩子、再压左孩子；后进先出的性质保证左孩子先于右孩子弹出，因此输出始终遵循根—左—右。

正确性依据

初始时根是第一个待访问节点。每次循环恰好访问一个待处理节点，并把它的右、左子树根按相反入栈顺序加入待处理集合。于是下一次优先完成左子树，左子树结束后才轮到右子树；归纳可知得到的正是前序遍历。

代码实现

C++

C++17

class Solution {
public:
    std::vector<int> preorderTraversal(TreeNode* root) {
        std::vector<int> answer;
        if (root == nullptr) {
            return answer;
        }

        std::stack<TreeNode*> nodes;
        nodes.push(root);
        while (!nodes.empty()) {
            TreeNode* node = nodes.top();
            nodes.pop();
            answer.push_back(node->val);
            if (node->right != nullptr) {
                nodes.push(node->right);
            }
            if (node->left != nullptr) {
                nodes.push(node->left);
            }
        }
        return answer;
    }
};

Python

Python 3

from typing import Optional


class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        if root is None:
            return []

        answer: list[int] = []
        nodes = [root]
        while nodes:
            node = nodes.pop()
            answer.append(node.val)
            if node.right is not None:
                nodes.append(node.right)
            if node.left is not None:
                nodes.append(node.left)
        return answer

复杂度分析

每个节点入栈、出栈各一次，时间复杂度为 O(n)。最坏情况下栈保存一条根到叶路径，空间复杂度为 O(h)，其中 h 是树高。

易错点

• 将左孩子先压栈会得到根—右—左的顺序。
• 忘记空树判断，随后访问空指针。
• 把“压入顺序”和“输出顺序”当成同一个顺序。

模式迁移

需要在首次到达节点时记录路径、深度或前缀状态时，前序的“弹出即处理”位置可以直接承载这些状态。