js实现前序遍历

前序遍历简介

前序遍历（Pre-order Traversal）是二叉树遍历的一种方式，遍历顺序为：根节点 → 左子树 → 右子树。常用于复制树结构或表达式的序列化。

递归实现

递归是最直观的实现方式，代码简洁易懂：

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) {
    if (!root) return [];
    const stack = [root];
    const result = [];
    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) {
    let curr = root;
    const result = [];
    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 遍历会修改原始树结构，必要时需恢复。

复杂度对比

其中 h 为树的高度，n 为节点数量。