LeetCode 144. 二叉树的前序遍历

约 4 分钟
文章信息 20 个分类 5 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 50-100 字节跳动 微软 美团 阿里巴巴 快手 腾讯 百度 滴滴 京东 华为 拼多多 网易 小米 虾皮
标签
深度优先搜索 树 二叉树 栈 前序遍历
目录

题目描述

✅ 144. 二叉树的前序遍历

image-20230305165126109

image-20230305165122479

题意分析

给定二叉树的根节点，要求返回前序遍历的节点值序列。前序的定义是「根 → 左子树 → 右子树」：先访问当前节点，再完整走完左子树，最后走完右子树。

题目带一个明确的进阶信号：递归写法很简单，请用迭代完成。也就是说这题真正想考的不是「会不会背遍历顺序」，而是能不能不靠函数调用、自己手动维护遍历状态。

约束很宽松：节点数在 $[0, 100]$，节点值在 $[-100, 100]$。规模小意味着不卡性能，卡的是写法本身；唯一必须处理的边界是空树，此时应返回空列表而不是 null。

解法：栈模拟前序遍历

核心思路

问题关键：前序顺序是「根、左、右」。递归能直接表达这个顺序，但题目进阶要求迭代，因此要用显式栈保存尚未访问的子树。

为什么选栈：栈的后进先出与递归调用栈一致。弹出节点时立即记录它的值，再把孩子压栈，就实现了「先访问根，再展开子树」。

不变量：栈顶始终是前序序列中下一个应访问的节点。因为左子树必须先于右子树，而栈后进先出，所以要先压右孩子，再压左孩子；这样下一次弹出的才是左孩子。每个非空节点只会入栈、出栈一次，因此不会遗漏或重复。

解题步骤

  • 空树直接返回空结果；非空时将根节点压栈。
  • 栈非空时弹出栈顶，把节点值加入结果。
  • 依次把非空的右孩子、左孩子压栈，保证左孩子先被处理。
  • 栈空时所有节点都已访问，返回结果。

例如根节点的左右孩子分别为 2、3：访问根后先压 3、再压 2，下一次弹出的是 2，顺序自然是「根、左、右」。

代码实现

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

        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);

            // 右孩子先入栈，左孩子才能先出栈访问。
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }

        return res;
    }
}

func preorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    if root == nil {
        return res
    }

    stack := []*TreeNode{root}
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, node.Val)

        // 栈后进先出，因此按右、左顺序压栈。
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
    }

    return res
}

复杂度分析

  • 时间复杂度：$O(n)$，每个节点访问一次。
  • 空间复杂度：$O(h)$，h 为树高；最坏退化为 $O(n)$。返回结果占 $O(n)$，通常不计入额外空间。

关键点总结

  • 前序迭代的访问时机是「出栈即访问」。
  • 期望先访问的节点要后入栈，所以孩子按「右、左」顺序压栈。
  • 显式栈模拟的是递归调用栈；若面试官不要求迭代，递归版更短，但复杂度相同。
  • 只让非空节点入栈，循环体无需额外处理 null。

易错点总结

  • 先压左再压右会得到「根、右、左」；[1,2,3] 会错误输出 [1,3,2]。
  • 空树不能把 null 压入 ArrayDeque，应直接返回空结果。
  • 访问值应发生在节点出栈时；孩子入栈时就记录会打乱整棵子树的顺序。
  • 用队列会变成层序遍历，不能替代栈。

相似题目

题目 难度 考察点
94. 二叉树的中序遍历 简单 访问时机换到左链走完之后，栈模拟比前序更绕
145. 二叉树的后序遍历 简单 迭代版最难的一个，可用「根右左」再反转的技巧
589. N 叉树的前序遍历 简单 孩子从两个变成列表，压栈需按孩子逆序
590. N 叉树的后序遍历 简单 N 叉树上复用「前序变体再反转」的思路
102. 二叉树的层序遍历 中等 数据结构从栈换成队列，遍历维度从深度变成层