JS二叉树前中后序遍历全解析

本文详解了使用JavaScript实现二叉树前序、中序和后序遍历的各种方法，重点介绍了递归与迭代两种实现思路。三种遍历方式的根本区别在于根节点、左子树和右子树的访问顺序：前序（根左右）、中序（左根右）、后序（左右根）。文章深入剖析了递归实现的简洁性以及迭代实现中栈结构的巧妙运用，例如前序遍历的单栈法、中序遍历的持续入栈回溯法，以及后序遍历的双栈逆序法。掌握这些遍历方法是理解和操作树形数据结构的关键，也是提升算法能力的重要一步。通过本文，你将能够熟练运用JavaScript实现二叉树的各种遍历，为解决更复杂的算法问题打下坚实基础。

在JavaScript中实现二叉树的前中后序遍历，主要通过递归或迭代方法完成，核心区别在于访问根、左子树和右子树的顺序：前序为根左右，中序为左根右，后序为左右根；递归实现简洁直观，而迭代实现分别利用栈结构模拟调用过程，其中前序使用单一栈并先入右子节点再入左子节点，中序通过持续入栈左子节点并在回溯时访问，后序则可通过双栈法将前序的根右左逆序变为左右根，最终实现三种遍历方式的正确输出，完整掌握这些方法是处理树形结构的基础，也是算法进阶的关键步骤。

在JavaScript中实现二叉树的前中后序遍历，主要依赖递归或借助栈的迭代方法。这三种遍历方式的核心区别在于访问根节点、左子树和右子树的相对顺序。理解并掌握它们，是处理树形数据结构的基础，也是许多复杂算法的起点。

解决方案

我们先定义一个简单的二叉树节点结构，这样后续的代码会更清晰：

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

接下来，我们看看前中后序的实现。

前序遍历 (Pre-order Traversal): 根 -> 左 -> 右

前序遍历的逻辑是先访问当前节点，然后递归地访问左子树，最后访问右子树。

递归实现： 这是最直观的方式，代码非常简洁。

function preorderTraversalRecursive(root, result = []) {
    if (!root) {
        return result;
    }
    result.push(root.val); // 访问根节点
    preorderTraversalRecursive(root.left, result); // 遍历左子树
    preorderTraversalRecursive(root.right, result); // 遍历右子树
    return result;
}

迭代实现： 使用一个栈来模拟递归的过程。我的思路是，先将根节点入栈。然后在一个循环里，每次弹出栈顶元素，访问它，接着先将右子节点入栈（如果存在），再将左子节点入栈（如果存在）。这样做的原因是，栈是后进先出（LIFO），为了先处理左子树，我们必须先让左子树的根在栈顶。

function preorderTraversalIterative(root) {
    const result = [];
    if (!root) {
        return result;
    }
    const stack = [root];
    while (stack.length > 0) {
        const node = stack.pop();
        result.push(node.val);
        // 先推右孩子，再推左孩子，确保左孩子先被处理
        if (node.right) {
            stack.push(node.right);
        }
        if (node.left) {
            stack.push(node.left);
        }
    }
    return result;
}

中序遍历 (In-order Traversal): 左 -> 根 -> 右

中序遍历是先访问左子树，然后访问当前节点，最后访问右子树。对于二叉搜索树（BST）来说，中序遍历的结果是一个有序序列，这特性蛮有意思的。

递归实现：

function inorderTraversalRecursive(root, result = []) {
    if (!root) {
        return result;
    }
    inorderTraversalRecursive(root.left, result); // 遍历左子树
    result.push(root.val); // 访问根节点
    inorderTraversalRecursive(root.right, result); // 遍历右子树
    return result;
}

迭代实现： 这个实现稍微需要一点技巧。我们需要一直向左走，将遇到的节点压入栈中。当无法再向左走时，弹出栈顶节点并访问它，然后转向其右子树。

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

    while (current || stack.length > 0) {
        // 一直向左，并将节点入栈
        while (current) {
            stack.push(current);
            current = current.left;
        }
        // 弹出栈顶节点，它是当前子树中最左的未访问节点
        current = stack.pop();
        result.push(current.val);
        // 转向右子树
        current = current.right;
    }
    return result;
}

后序遍历 (Post-order Traversal): 左 -> 右 -> 根

后序遍历是先访问左子树，然后访问右子树，最后访问当前节点。这个遍历方式在释放资源或构建表达式树时比较常用。

递归实现：

function postorderTraversalRecursive(root, result = []) {
    if (!root) {
        return result;
    }
    postorderTraversalRecursive(root.left, result); // 遍历左子树
    postorderTraversalRecursive(root.right, result); // 遍历右子树
    result.push(root.val); // 访问根节点
    return result;
}

迭代实现： 后序遍历的迭代实现通常被认为是最复杂的。一种比较直观的方法是使用两个栈。第一个栈用于模拟前序遍历的逆过程（根右左），第二个栈则收集第一个栈弹出的元素，最终第二个栈的元素顺序就是后序遍历的结果。

function postorderTraversalIterative(root) {
    const result = [];
    if (!root) {
        return result;
    }
    const stack1 = [root];
    const stack2 = []; // 用于存储最终结果的逆序

    while (stack1.length > 0) {
        const node = stack1.pop();
        stack2.push(node.val); // 将节点值推入第二个栈
        // 先推左孩子，再推右孩子，确保右孩子先被处理
        if (node.left) {
            stack1.push(node.left);
        }
        if (node.right) {
            stack1.push(node.right);
        }
    }
    // stack2 此时存储的是 "根右左" 的逆序，即 "左右根"
    return stack2.reverse();
}

这个双栈方法虽然多用了一个栈，但在理解上比单栈的复杂判断要容易些，我个人觉得在初学时更友好。

本篇关于《JS二叉树前中后序遍历全解析》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！