实现js前序遍历

前序遍历简介

前序遍历是二叉树遍历的一种方式，遍历顺序为根节点、左子树、右子树。在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;
}

注意事项

递归实现代码简洁但可能存在栈溢出风险，适合深度较小的树。迭代实现通过显式栈避免了递归的潜在问题，适合深度较大的树结构。两种方法时间复杂度均为O(n)，空间复杂度取决于树的结构。