0144.二叉树的前序遍历

难度：🟢 简单

标签：栈、树、深度优先搜索、二叉树、递归

链接：144. 二叉树的前序遍历

题目描述

给你二叉树的根节点 root ，返回它节点值的 前序遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

解题思路

核心思想

本题的核心是实现二叉树的 前序遍历。前序遍历的访问顺序是：根节点 -> 左子树 -> 右子树。这种遍历方式会优先访问每一棵子树的根节点。

思路选择

递归法 是实现前序遍历最直接、最简洁的方式。算法的结构直接遵循了前序遍历的定义（根-左-右），代码逻辑清晰。

关键步骤

1. 递归的终止条件 (Base Case)：如果当前节点 root 为 null，意味着到达了树的尽头，没有节点可访问，直接返回一个空数组。

2. 递归分解： a. 首先，访问 根节点，获取其值 root.val。 b. 接着，递归地对当前节点的 左子树 进行前序遍历，获取左子树的遍历结果。 c. 最后，递归地对当前节点的 右子树 进行前序遍历，获取右子树的遍历结果。

3. 结果合并：按照“根-左-右”的顺序，将根节点的值、左子树的遍历结果、右子树的遍历结果拼接起来，形成最终的前序遍历序列。

代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 * this.val = (val===undefined ? 0 : val)
 * this.left = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
    if (root === null) return [];

    return [root.val, ...preorderTraversal(root.left), ...preorderTraversal(root.right)];
};

复杂度分析

• 时间复杂度：O(n) 其中 n 是树的节点总数。每个节点都会被访问一次。

• 空间复杂度：O(h) 其中 h 是树的高度。空间复杂度主要由递归调用栈的深度决定。在最坏情况下（树退化为一条链），空间复杂度为 O(n)；在最好的情况下（一个完全平衡的树），空间复杂度为 O(log n)。

相关题目

• 0094.二叉树的中序遍历

• 0145.二叉树的后序遍历

• 0102.二叉树的层序遍历

总结

前序遍历是三种主要的深度优先遍历方式之一，常用于创建树的副本或序列化树的结构。其递归实现非常直观，是学习树遍历算法的起点。与中序和后序遍历一样，前序遍历也可以通过迭代（使用栈）的方式来实现，这也是面试中需要掌握的技能。