在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();
}这个双栈方法虽然多用了一个栈，但在理解上比单栈的复杂判断要容易些，我个人觉得在初学时更友好。
