二叉树有哪几种遍历方式？前中后序和层序有什么区别？

简化版

二叉树遍历分两大类：深度优先（DFS） 和 广度优先（BFS）。DFS 按访问根节点的时机分为前序（根左右）、中序（左根右）、后序（左右根）；BFS 就是层序遍历（一层一层从上到下、从左到右）。前中后序天然适合递归，层序用队列实现。

详细版

「前/中/后」指的是根节点在什么时候被访问，左右子树永远是「先左后右」：

遍历	顺序	访问根的时机
前序 Preorder	根 → 左 → 右	最先访问根
中序 Inorder	左 → 根 → 右	中间访问根
后序 Postorder	左 → 右 → 根	最后访问根
层序 Levelorder	逐层，左到右	按层，用队列

以这棵树为例：

前序：1 2 4 5 3
中序：4 2 5 1 3
后序：4 5 2 3 1
层序：1 2 3 4 5

前中后序都可以用递归（几行代码）或用栈的迭代实现；层序用队列。

完整版教学

一、DFS 三种序的本质：只差一行的位置

前中后序的递归代码几乎一模一样，区别仅在「访问根节点那一行」放在递归左右子树的前、中、后：

void preorder(TreeNode r) {   // 前序
    if (r == null) return;
    visit(r);                 // 根在最前
    preorder(r.left);
    preorder(r.right);
}
void inorder(TreeNode r) {    // 中序
    if (r == null) return;
    inorder(r.left);
    visit(r);                 // 根在中间
    inorder(r.right);
}
void postorder(TreeNode r) {  // 后序
    if (r == null) return;
    postorder(r.left);
    postorder(r.right);
    visit(r);                 // 根在最后
}

理解这点，三种遍历就不用死记——只是「什么时候处理当前节点」的差别。

二、每种遍历的典型用途

前序（根最先）：适合「先处理父、再处理子」的场景，如复制/序列化一棵树（先建根再建子树）。
中序（左根右）：对二叉搜索树（BST） 做中序遍历，得到的是升序序列——这是 BST 最重要的性质，验证 BST、找第 K 小都靠它。
后序（根最后）：适合「先处理完子树再处理父」的场景，如计算子树高度/删除/释放一棵树、树形 DP（子树信息汇总到父节点）。
层序（逐层）：求树的深度、每层信息、最短路径、按层输出。

三、层序遍历（BFS）为什么用队列

层序要「先访问的节点，其孩子也先被访问」，这正是先进先出——用队列：根入队，然后循环「出队一个、把它的左右孩子入队」，直到队空。要按层分组时，每轮记录当前队列大小 size，一次性处理这一整层。

void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();          // 当前层的节点数
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            visit(node);
            if (node.left != null)  q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        // 这里是一层的分界
    }
}

四、递归遍历的本质是栈

前中后序递归其实是借助系统调用栈完成的。所以它们都能改写成用显式栈的迭代版本，避免深树递归导致栈溢出。DFS 用栈（LIFO）、BFS 用队列（FIFO），这是两者最根本的实现区别。

五、复杂度

所有遍历都是时间 O(n)（每个节点访问一次）。空间上：递归/迭代 DFS 是 O(h)（h 为树高，最坏 O(n)）；层序 BFS 是 O(w)（w 为最宽一层的节点数，最坏 O(n)）。

六、常见误区与追问

遍历	数据结构/调用方式	高频用途
前序 DFS	递归或栈	复制树、序列化、先处理根
中序 DFS	递归或栈	BST 升序、验证 BST
后序 DFS	递归或栈	求高度、树形 DP、删除释放
层序 BFS	队列	按层输出、最小深度、右视图

记忆钩子：前中后序的差别只是「访问根」相对左右子树的位置；DFS 和 BFS 的差别是栈与队列带来的访问形态。

误区：中序遍历任何二叉树都会有序。 只有满足左小右大的二叉搜索树，中序结果才是升序；普通二叉树没有排序语义。
误区：层序遍历也是 DFS 的一种。 层序按距离根的层数推进，是 BFS，核心数据结构是队列。
误区：递归遍历没有空间复杂度。 递归依赖系统调用栈，空间是 O(h)，退化树会到 O(n)。
误区：后序只是输出顺序不同，没有实际用途。 后序能先拿到子树结果，非常适合高度、平衡、直径、最大路径和等树形 DP。
追问：为什么前序适合序列化？ 先记录根节点，再递归记录左右子树，配合空节点标记可以唯一还原结构。
追问：怎么选择 DFS 还是 BFS？ 需要沿路径递归求子树信息时用 DFS；需要按层、最短层数或层级视图时优先 BFS。

七、加强记忆

二叉树遍历分 DFS（前序根左右、中序左根右、后序左右根——区别只在「访问根」放在递归左右的前/中/后）和 BFS（层序，用队列逐层）。用途记忆：前序=复制/序列化，中序=BST 得升序，后序=树形 DP/求高度，层序=深度/按层。DFS 靠栈、BFS 靠队列，都是 O(n) 时间。

简化版

详细版