二叉树的前序、中序、后序、层序遍历，递归和迭代实现
❓ 什么是二叉树遍历？
二叉树遍历是按照特定顺序访问树中所有节点的过程。 根据访问根节点的时机，分为三种深度优先遍历： - **前序遍历（Preorder）**：根 → 左 → 右 - **中序遍历（Inorder）**：左 → 根 → 右 - **后序遍历（Postorder）**：左 → 右 → 根 还有一种广度优先遍历： - **层序遍历（Level Order）**：逐层从左到右访问
🎯 为什么使用？
不同遍历方式适用于不同场景： **前序遍历**： - 复制/序列化树结构 - 打印树结构（父节点优先） - 求解前缀表达式 **中序遍历**： - BST 得到有序序列 - 表达式树得到中缀表达式 - 二叉搜索树验证 **后序遍历**： - 删除树（先删子节点） - 计算目录大小（先算子目录） - 表达式求值 **层序遍历**： - 计算层数/最大宽度 - 按层打印 - 寻找最近的目标节点
⚙️ 如何工作？
**递归实现**
递归是最直观的方式，三种遍历只是调整代码顺序：
```
function traverse(node) {
if (!node) return;
// result.push(node.val); // 前序：这里处理
traverse(node.left);
// result.push(node.val); // 中序：这里处理
traverse(node.right);
// result.push(node.val); // 后序：这里处理
}
```
**迭代实现（使用栈）**
核心思想：用栈模拟递归调用栈
```
// 中序遍历迭代
while (curr || stack.length) {
while (curr) { // 一路向左
stack.push(curr);
curr = curr.left;
}
curr = stack.pop(); // 回溯
result.push(curr.val); // 访问
curr = curr.right; // 转向右子树
}
```
**层序遍历（使用队列）**
```
queue.push(root);
while (queue.length) {
const size = queue.length; // 记录当前层节点数
for (let i = 0; i < size; i++) {
const node = queue.shift();
// 处理当前节点
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
```
🎨 形象比喻
「想象你在参观一棵家谱树： - **前序遍历**：像自上而下介绍，先介绍爷爷，再介绍爸爸和叔叔 - **中序遍历**：像年龄排序，先介绍最小的孙子，然后父亲，再伯伯... - **后序遍历**：像从下往上汇报，先汇报子女情况，最后汇报自己 - **层序遍历**：像拍集体照，一排一排站好，按排拍照」
🔍 识别关键词
当你在题目中看到以下关键词时，考虑使用二叉树遍历：
遍历前序中序后序层序深度路径
📊 时间空间复杂度
时间复杂度
O(n)
空间复杂度
O(h) 递归 / O(n) 层序
访问所有节点，递归空间取决于树高，层序最多存一层节点
按?查看快捷键