二叉树的前序遍历

题目描述

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

前序遍历：根 → 左 → 右

示例

示例 1：

输入: root = [1,null,2,3]

    1
     \
      2
     /
    3

输出: [1, 2, 3]

示例 2：

输入: root = []
输出: []

示例 3：

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

示例 4：

输入: root = [1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9]

       1
     /   \
    2     3
   / \     \
  4   5     8
     / \   /
    6   7 9

输出: [1, 2, 4, 5, 6, 7, 3, 8, 9]

解题思路

前序遍历的顺序是「根 → 左 → 右」，即先访问根节点，再访问左子树，最后访问右子树。

递归法：从根节点开始，将当前节点值加入结果，然后递归访问左子树，再递归访问右子树。

迭代法（用栈模拟）：由于栈是后进先出，为了让左子树先访问，需要先将右子节点入栈，再将左子节点入栈。这样出栈时就是先左后右。

代码实现

/**
 * 方法一：递归版前序遍历
 * @param {TreeNode} root - 二叉树根节点
 * @returns {number[]} 前序遍历结果（根→左→右）
 */
function preorderRecursive(root) {
    const result = [];
    const dfs = (node) => {
        if (!node) return;
        result.push(node.val);       // 根
        if (node.left) dfs(node.left);   // 左
        if (node.right) dfs(node.right); // 右
    };
    dfs(root);
    return result;
}

/**
 * 方法二：迭代版前序遍历（用栈模拟）
 * @param {TreeNode} root - 二叉树根节点
 * @returns {number[]} 前序遍历结果
 */
function preorderIterative(root) {
    if (!root) return [];
    const result = [];
    const stack = [root];
    while (stack.length > 0) {
        const node = stack.pop();
        result.push(node.val);              // 根
        if (node.right) stack.push(node.right); // 右先入栈（后出）
        if (node.left) stack.push(node.left);   // 左后入栈（先出）
    }
    return result;
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为节点数，每个节点访问一次。
• 空间复杂度：递归版 O(h)，h 为树的高度（递归栈深度）；迭代版 O(h)，栈中最多存储 h 个节点。最坏情况（链状树）为 O(n)。

root = [1,null,2,3]

[1,2,3]