树的遍历

本文主要围绕讲解数据结构中“树”是怎么遍历的，一棵“会讲故事”的二叉树，带你把前序 / 中序 / 后序 / 层序、以及 DFS / BFS 一网打尽。

先立个主角：

    A
   / \
  B   C
 / \   \
D   E   F

把遍历想成“参观一座带分叉走廊的博物馆”。节点是房间，左右子树是左/右走廊。不同遍历，就像不同的参观路线与礼仪顺序。

我们首先看名字前序、中序、后序，怎么定义前中后呢？关键点在于遍历根节点的位置。根节点在前则为前序，以此类推。

前序遍历（Preorder）：根 → 左 → 右

参观比喻：到一个房间，先和房主打招呼（访问根），再去左边的房间串门（左子树），最后去右边（右子树）。

顺序：A, B, D, E, C, F

适用场景：

• “打包”结构（序列化/复制目录）——先记当前，再记子结构。

• 目录树打印：先标题，再子内容。

  void preorderRec(TreeNode* root, vector<int>& out) {
    if (!root) return;
    out.push_back(root->val);
    preorderRec(root->left, out);
    preorderRec(root->right, out);
  }
  

中序遍历（Inorder）：左 → 根 → 右（仅二叉树有明确定义）

参观比喻：先把左边所有房间逛完，再回来与房主交谈（根），最后逛右边。

顺序：D, B, E, A, C, F

黄金定律：二叉搜索树（BST）的中序遍历一定是递增有序。 适用场景：

• 升序输出所有键值
• 找第 k 小元素
• 验证是否为 BST

// 中序：左-根-右（BST 中序有序）
void inorderRec(TreeNode* root, vector<int>& out) {
    if (!root) return;
    inorderRec(root->left, out);
    out.push_back(root->val);
    inorderRec(root->right, out);
}

后序遍历（Postorder）：左 → 右 → 根

参观比喻：先把孩子们收拾好（左右房间），最后家长收尾（根）。像打扫屋子：先清理各房间，再关门锁屋（根）。

顺序：D, E, B, F, C, A

适用场景：

• 需要自底向上汇总：计算子树规模/高度、动态规划
• 释放资源 / 删除整棵树（先删孩子，再删父）

// 后序：左-右-根（自底向上）
void postorderRec(TreeNode* root, vector<int>& out) {
    if (!root) return;
    postorderRec(root->left, out);
    postorderRec(root->right, out);
    out.push_back(root->val);
}

层序遍历（Level-order）：一层一层，从左到右

参观比喻（广场合影）：按楼层排队，先一楼再二楼；同层从左到右点名。

顺序：A, B, C, D, E, F

数据结构：队列（queue）——先来先服务。

适用场景：

• 最短步数/最少层数问题（无权边）
• 层级打印（例如公司组织架构、分层汇总）

深度优先（DFS）vs 广度优先（BFS）

DFS（Depth-First Search）：一条路走到黑再回头。实现常见有三种“礼仪次序”：前/中/后序。

BFS（Breadth-First Search）：按层推进。

一句话：前/中/后序都是 DFS 的不同“拜访时机”；层序就是 BFS。