当前位置：首页 > JavaScript

实现js前序遍历

2026-04-04 14:24:10JavaScript

前序遍历简介

前序遍历是二叉树遍历的一种方式，遍历顺序为：根节点 → 左子树 → 右子树。以下是实现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)的算法，通过临时修改树结构实现遍历。

实现js前序遍历

function preorderTraversal(root) {
    const result = [];
    let current = root;

    while (current) {
        if (!current.left) {
            result.push(current.val);
            current = current.right;
        } else {
            let predecessor = current.left;
            while (predecessor.right && predecessor.right !== current) {
                predecessor = predecessor.right;
            }

            if (!predecessor.right) {
                result.push(current.val);
                predecessor.right = current;
                current = current.left;
            } else {
                predecessor.right = null;
                current = current.right;
            }
        }
    }
    return result;
}