JS如何实现二叉树遍历？前中后序遍历

在JavaScript中，二叉树的遍历（前序、中序、后序）可通过递归或迭代实现，核心区别在于访问根、左、右子树的顺序。以下是具体实现方法：

• 递归实现：先访问根节点，再递归左、右子树。

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

• 迭代实现：用栈模拟递归，先压右子节点再压左子节点（保证左子树先处理）。

  function preorderTraversalIterative(root) { const result = []; if (!root) return result; const stack = [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;}

• 递归实现：先递归左子树，再访问根节点，最后递归右子树。

  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) { while (current) { // 一直向左入栈 stack.push(current); current = current.left; } current = stack.pop(); // 弹出最左节点 result.push(current.val); // 访问根 current = current.right; // 转向右子树 } return result;}

• 递归实现：先递归左、右子树，最后访问根节点。

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

• 迭代实现（双栈法）：

  栈1模拟前序的逆过程（根→右→左），栈2收集结果并反转。

  function postorderTraversalIterative(root) { const result = []; if (!root) return result; const stack1 = [root], stack2 = []; while (stack1.length) { const node = stack1.pop(); stack2.push(node.val); // 根右左顺序入栈2 if (node.left) stack1.push(node.left); // 左子节点先入栈1 if (node.right) stack1.push(node.right); // 右子节点后入栈1 } return stack2.reverse(); // 反转得到左右根}

• 递归：代码简洁，但可能因递归深度过大导致栈溢出。
• 迭代：通过栈模拟调用过程，避免递归开销，但逻辑稍复杂。
• 双栈法后序遍历：利用前序逆序的思想，降低单栈实现的复杂度。

掌握这些方法后，可进一步优化迭代实现（如后序遍历的单栈法），或扩展至层次遍历等更复杂的树操作。