实现js前序遍历

前序遍历简介

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

递归实现

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

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遍历节省空间但会修改树结构。根据实际需求选择合适的方法。