当前位置：首页 > JavaScript

实现js前序遍历

2026-03-01 13:40:30JavaScript

前序遍历简介

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

递归实现

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

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;
}