四种遍历

    A
   / \
  B   C
 / \   \
D   E   F

遍历	顺序	结果
先序（Preorder）	根 → 左 → 右	A B D E C F
中序（Inorder）	左 → 根 → 右	D B E A C F
后序（Postorder）	左 → 右 → 根	D E B F C A
层序（Level Order）	按层从左到右	A B C D E F

记忆：名字说的是根在什么时候被访问。

关键性质：

中序遍历 BST → 得到有序序列（BST 的核心性质）
先序 + 中序 或 后序 + 中序 → 唯一确定一棵二叉树
先序 + 后序 → 不能唯一确定（除非是满二叉树）

递归实现

struct Node { int val; Node *l, *r; };

void preorder(Node* u) {
    if (!u) return;
    visit(u);              // 先序：先访问根
    preorder(u->l);
    preorder(u->r);
}

void inorder(Node* u) {
    if (!u) return;
    inorder(u->l);
    visit(u);              // 中序：中间访问根
    inorder(u->r);
}

void postorder(Node* u) {
    if (!u) return;
    postorder(u->l);
    postorder(u->r);
    visit(u);              // 后序：最后访问根
}

三者的代码完全一样，只有 visit 的位置不同——这就是"根在什么时候访问"的具体体现。

迭代实现

递归写法简洁，但深度大时会爆栈。迭代版用显式栈。

先序（栈）

void preorder_iter(Node* root) {
    if (!root) return;
    stack<Node*> st;
    st.push(root);
    while (!st.empty()) {
        Node* u = st.top(); st.pop();
        visit(u);
        if (u->r) st.push(u->r);      // 注意：先压右，后压左
        if (u->l) st.push(u->l);      // 这样弹出时左先被访问
    }
}

为什么先压右孩子：栈是后进先出，要左孩子先被访问，就得后压左孩子。

中序（栈）

void inorder_iter(Node* root) {
    stack<Node*> st;
    Node* cur = root;
    while (cur || !st.empty()) {
        while (cur) {                 // 一路向左，沿途入栈
            st.push(cur);
            cur = cur->l;
        }
        cur = st.top(); st.pop();
        visit(cur);                   // 左子树完了，访问根
        cur = cur->r;                 // 转向右子树
    }
}

思路：模拟递归的"走到最左 → 访问 → 处理右子树"。

后序（栈 + 前一节点）

void postorder_iter(Node* root) {
    stack<Node*> st;
    Node* cur = root, *last = nullptr;
    while (cur || !st.empty()) {
        while (cur) { st.push(cur); cur = cur->l; }
        Node* peek = st.top();
        // 右子树存在且还没处理 → 转向右子树
        if (peek->r && last != peek->r) {
            cur = peek->r;
        } else {
            visit(peek);
            last = peek;
            st.pop();
        }
    }
}

判断何时能访问根：右子树为空，或右子树刚被访问完。用 last 记录上一个访问的节点。

另一个技巧：后序 = 先序（根右左）的逆序。做"根→右→左"的遍历再反转即可，代码简单很多。

层序（队列）

void levelorder(Node* root) {
    if (!root) return;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* u = q.front(); q.pop();
        visit(u);
        if (u->l) q.push(u->l);
        if (u->r) q.push(u->r);
    }
}

按层处理（很多题需要知道当前在第几层）：

int level = 0;
while (!q.empty()) {
    int sz = q.size();              // 当前层的节点数
    for (int i = 0; i < sz; i++) {  // 只处理这一层
        Node* u = q.front(); q.pop();
        visit(u);
        if (u->l) q.push(u->l);
        if (u->r) q.push(u->r);
    }
    level++;
}

应用：求树的高度、每层最大值、锯齿形遍历、右视图。

Morris 遍历

$O(1)$ 额外空间的中序遍历（不用栈、不用递归）。

核心技巧：利用叶子节点的空指针，临时指向中序后继，遍历完再恢复。

void morris_inorder(Node* root) {
    Node* cur = root;
    while (cur) {
        if (!cur->l) {
            visit(cur);               // 没有左子树，直接访问
            cur = cur->r;
        } else {
            // 找到 cur 的中序前驱（左子树的最右节点）
            Node* pred = cur->l;
            while (pred->r && pred->r != cur) pred = pred->r;

            if (!pred->r) {           // 第一次到 cur：建立线索
                pred->r = cur;
                cur = cur->l;
            } else {                  // 第二次到 cur：左子树已遍历完
                pred->r = nullptr;    // 恢复树结构
                visit(cur);
                cur = cur->r;
            }
        }
    }
}

复杂度： $O(n)$ 时间（每条边最多走常数次）， $O(1)$ 空间。

代价：遍历过程中临时修改树结构（虽然会恢复）。并发场景或未恢复就中断会破坏树。

实际价值：面试常考，工程中很少用（代码复杂、常数大）。

由遍历序列重建二叉树

先序 + 中序

先序: [根][左子树先序][右子树先序]
中序: [左子树中序][根][右子树中序]

1. 先序第一个是根
2. 在中序里找到根的位置 k
3. 中序中 k 左边是左子树（长度 k），右边是右子树
4. 递归

Node* build(vector<int>& pre, vector<int>& in, int pl, int pr, int il, int ir) {
    if (pl > pr) return nullptr;
    int rootVal = pre[pl];
    Node* root = new Node(rootVal);
    int k = il;
    while (in[k] != rootVal) k++;
    int leftSize = k - il;
    root->l = build(pre, in, pl + 1, pl + leftSize, il, k - 1);
    root->r = build(pre, in, pl + leftSize + 1, pr, k + 1, ir);
    return root;
}

优化：用哈希表存"值 → 中序下标"，把查找从 $O(n)$ 降到 $O(1)$ ，整体 $O(n)$ 。

后序 + 中序

类似，但根在后序的最后一个。

为什么先序 + 后序不够

先序: A B     后序: B A
可能:             也可能:
   A                 A
  /                   \
 B                     B

无法确定 B 是左孩子还是右孩子。若为满二叉树（每个节点 0 或 2 个孩子）则可以确定。

DFS 序（Euler Tour）

把树"拍平"成一个序列，子树对应序列上的连续区间。

int timer = 0, tin[N], tout[N], euler[N];

void dfs(int u, int p) {
    tin[u] = ++timer;              // 进入 u
    euler[timer] = u;
    for (int v : g[u]) {
        if (v == p) continue;
        dfs(v, u);
    }
    tout[u] = timer;               // 离开 u（注意不是 ++timer）
}

性质： $u$ 的子树对应 euler[tin[u] .. tout[u]] 这一段。

用途：

子树统计：子树和 = 区间和 → 用树状数组/前缀和
子树修改：区间加 → 用差分
判祖先：tin[u] <= tin[v] && tout[v] <= tout[u]

把树上的"子树问题"转化为数组上的"区间问题"
这是树上算法最重要的一次转化

子树求和示例

// 给 u 的子树所有节点 +v，查询某节点的值
// 1. DFS 序 → 子树变成连续区间
// 2. 区间加 → 差分数组
// 3. 单点查 → 前缀和
diff[tin[u]] += v;
diff[tout[u] + 1] -= v;

括号序列 / 欧拉环游

另一种 DFS 序：进入和离开都记录。

void dfs(int u, int p) {
    seq.push_back(u);              // 进入
    for (int v : g[u]) {
        if (v == p) continue;
        dfs(v, u);
        seq.push_back(u);          // 回到 u
    }
}

序列长度 $2n-1$ 。用途：某些树上路径问题、LCA 的 $\pm 1$ RMQ 解法。

树链剖分（Heavy-Light Decomposition）

把树剖成若干条重链，使得任意路径被拆成 $O(\log n)$ 段，每段是数组上的连续区间。

重儿子: 子树最大的那个孩子
重链:   沿重儿子连成的链
轻边:   其余的边

关键性质：从根到任意节点，经过的轻边不超过 $\log n$ 条（因为每走一条轻边，子树大小至少减半）。

int sz[N], dep[N], heavy[N], top[N], dfn[N], timer = 0;

void dfs1(int u, int p) {          // 第一遍：求 size 和重儿子
    sz[u] = 1; heavy[u] = -1;
    int mx = 0;
    for (int v : g[u]) {
        if (v == p) continue;
        dep[v] = dep[u] + 1;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > mx) { mx = sz[v]; heavy[u] = v; }
    }
}

void dfs2(int u, int topf) {       // 第二遍：剖分，优先走重儿子保证链上 dfn 连续
    top[u] = topf;
    dfn[u] = ++timer;
    if (heavy[u] != -1) dfs2(heavy[u], topf);        // 重儿子，同一条链
    for (int v : g[u]) {
        if (v == heavy[u] || dep[v] != dep[u] + 1) continue;
        dfs2(v, v);                                   // 轻儿子，新链
    }
}

// 路径查询/修改
void pathQuery(int u, int v) {
    while (top[u] != top[v]) {                        // 不在同一条链
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        query_range(dfn[top[u]], dfn[u]);             // 处理 [top[u], u] 这一段
        u = parent[top[u]];                           // 跳到链顶的父
    }
    if (dep[u] > dep[v]) swap(u, v);
    query_range(dfn[u], dfn[v]);                      // 最后同一条链
}

复杂度： $O(\log^2 n)$ 每次路径操作（ $O(\log n)$ 段 × 线段树 $O(\log n)$ ）。

应用：树上路径修改/查询、LCA（ $O(\log n)$ ）、子树操作。

两个 DFS 的顺序不能反：先算 sz 才能定重儿子，定了重儿子才能剖分。

遍历的应用

应用	遍历方式
求树高 / 深度	后序（自底向上汇总）
求子树大小	后序
复制树	先序（先建根）
释放树	后序（先删孩子再删根）
判断 BST 合法性	中序（应有序）
表达式求值	后序（先把操作数算出来）
序列化 / 反序列化	先序（含空节点标记）
二叉树最大宽度	层序
找最近公共祖先	后序（自底向上汇报）

规律：

需要"孩子的信息"才能算自己 → 后序；需要"父的信息"才能算自己 → 先序。

复杂度

操作	时间	空间
任意遍历	$O(n)$	$O(h)$ 递归栈 / $O(n)$ 显式栈
Morris 遍历	$O(n)$	$O(1)$
DFS 序	$O(n)$	$O(n)$
树链剖分	预处理 $O(n)$ ，路径 $O(\log^2 n)$	$O(n)$

常见坑

递归爆栈：退化成链时深度 $n$ 。 $n > 10^4$ 考虑迭代版或改非递归
迭代先序的压栈顺序：先压右后压左，别反了
迭代后序的 last 判断：漏了会导致右子树被重复访问或根被提前访问
Morris 遍历没恢复树：异常中断会留下悬空指针
层序遍历的层边界：q.size() 要在循环开始前取，循环里 q 在变
重建二叉树时的下标计算：pl + leftSize 之类的边界极易差一
空树 / 单节点：root == nullptr、size == 1 要单独验证
DFS 序的 tout[u] = timer：是"离开时的 timer"，不是 ++timer
树链剖分第二遍 DFS 的遍历条件：dep[v] != dep[u] + 1 用来排除父节点（比传 p 更简洁，但要保证初始化正确）
无根树遍历必须传父节点：否则会沿父边走回去，无限递归