二叉树的前序遍历

这是一道围绕树、二叉树展开的高频练习。建议先掌握「栈模拟前序」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

树

二叉树

原题练习

题目分析

这道题表面上是在处理「二叉树的前序遍历」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考树、二叉树这些能力。先别急着写代码，先把题目要求翻译成人话，明确结果是什么、约束是什么、过程里要持续维护什么。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：用栈显式模拟递归过程，每次先访问节点，再按右左顺序压栈，就能得到根左右的前序遍历。

推荐代码

推荐解法：栈模拟前序

时间复杂度： O(n)

空间复杂度： O(n)

核心思路：用栈显式模拟递归过程，每次先访问节点，再按右左顺序压栈，就能得到根左右的前序遍历。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);

            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }

        return result;
    }
}

结构化讲解

面试时怎么讲

开场思路

这题我会用栈来模拟递归版前序遍历。

核心过程

先把根节点压栈。
每次弹出栈顶节点并立刻访问。
然后先压右孩子，再压左孩子。
循环直到栈空，得到的顺序就是根左右。

复杂度总结

时间复杂度 O(n)，空间复杂度 O(n)。

面试补一句：面试里这题最容易出错的地方就是压栈顺序。

核心思路

前序遍历顺序是根、左、右。迭代写法的关键是利用栈的后进先出特性，先压右孩子、再压左孩子，这样左子树会先被弹出访问。

步骤讲解

根节点入栈

如果根不为空，先把根节点压入栈中，作为遍历起点。

为什么这样做：栈用来保存后续待访问的节点。

对应代码提示：stack.push(root);

弹栈即访问当前节点

每次从栈顶取出一个节点，立刻把值加入答案。

为什么这样做：前序遍历要求先访问根节点。

对应代码提示：TreeNode node = stack.pop(); result.add(node.val);

按右左顺序压栈

先压右孩子，再压左孩子，保证左子树优先被处理。

为什么这样做：栈是后进先出，压栈顺序要与访问顺序反着来。

对应代码提示：if (node.right != null) stack.push(node.right);

易错点

压栈顺序写成左右

这样弹栈时会变成先右后左，遍历顺序错误。

正确理解：牢记前序迭代是先压右，再压左。

把访问动作放到孩子处理之后

那样更像中序或后序，不再是前序。

正确理解：节点一弹出就立刻记录答案。

复杂度与适用判断

时间复杂度：O(n)

空间复杂度：O(n)

比其他方案更好在哪里：比递归更适合继续扩展成统一模板处理多种遍历。

适用判断：需要显式控制遍历顺序或避免递归栈时，优先考虑迭代写法。

额外提醒

栈里保存的是“稍后访问的节点”，不是路径答案。