js实现前序遍历

前序遍历简介

前序遍历（Preorder Traversal）是二叉树遍历的一种方式，顺序为：根节点 → 左子树 → 右子树。以下是 JavaScript 实现前序遍历的几种方法。

递归实现

递归是最直观的方法，代码简洁：

function preorderTraversal(root) {
    const result = [];
    function traverse(node) {
        if (!node) return;
        result.push(node.val); // 访问根节点
        traverse(node.left);   // 遍历左子树
        traverse(node.right);  // 遍历右子树
    }
    traverse(root);
    return result;
}

迭代实现（使用栈）

通过栈模拟递归过程，避免递归的调用栈开销：

function preorderTraversal(root) {
    const result = [];
    const stack = [];
    if (root) stack.push(root);
    while (stack.length) {
        const node = stack.pop();
        result.push(node.val); // 访问根节点
        // 右子树先入栈，保证左子树先处理
        if (node.right) stack.push(node.right);
        if (node.left) stack.push(node.left);
    }
    return result;
}

Morris 遍历

空间复杂度优化为 O(1)，通过临时修改树结构实现：

function preorderTraversal(root) {
    const result = [];
    let curr = root;
    while (curr) {
        if (!curr.left) {
            result.push(curr.val);
            curr = curr.right;
        } else {
            let predecessor = curr.left;
            while (predecessor.right && predecessor.right !== curr) {
                predecessor = predecessor.right;
            }
            if (!predecessor.right) {
                result.push(curr.val); // 访问根节点
                predecessor.right = curr;
                curr = curr.left;
            } else {
                predecessor.right = null;
                curr = curr.right;
            }
        }
    }
    return result;
}

注意事项

• 递归方法在树深度较大时可能导致栈溢出。
• 迭代方法通过显式栈结构更安全，适合大规模数据。
• Morris 遍历节省空间，但会修改原始树结构（临时性）。

根据需求选择合适的方法，递归适合简单场景，迭代和 Morris 适用于性能敏感场景。