在树的算法中，“欧拉序 (Euler Tour)” 和“DFS序 (DFS Order)” 是两种不同的遍历方式，虽然它们都基于 深度优先搜索。它们的核心区别在于 访问时机和记录内容不同，从而导致用途上的不同。

下面我们来分别解释它们，并比较区别。

## 一、DFS序（In-Time 和 Out-Time）
这是最常见的遍历方式，也称为 入栈序（in-time）/ 出栈序（out-time） 或者称为 进入时间/离开时间。

cpp
```
int timer = 0;
void dfs(int u, int parent) {
    in[u] = timer++;
    for (int v : tree[u]) {
        if (v != parent) dfs(v, u);
    }
    out[u] = timer;
}
```

### 特点：
每个节点只记录一次进入（in[u]）和离开（out[u]）的时刻。

子树 u 的所有节点 v 满足：`in[u] <= in[v] < out[u]`

子树大小 = `out[u] - in[u]`

**可以用来：**

判定一个点是否在某个子树中（通过时间范围）

扁平化整棵树，便于做区间查询（如 线段树、树状数组 (BIT)）

## 二、欧拉序（Euler Tour）
欧拉序是一种记录整条 DFS 遍历路径的方法。

cpp
```
vector<int> euler;

void euler_tour(int u, int parent) {
    euler.push_back(u);          // 第一次到达 u
    for (int v : tree[u]) {
        if (v != parent) {
            euler_tour(v, u);
            euler.push_back(u);  // 返回到 u 的时候再记一次
        }
    }
}
```

### 特点：
每个节点出现两次（进入、回溯）

整个 euler 数组长度是 `2n - 1`（对 n 个节点的树）

欧拉序对应的是“走过的路径”，适合做：

1. 最近公共祖先 LCA 查询（RMQ）

2. 处理“路径上”的问题

## DFS序 vs 欧拉序：区别总结
| 特性      | DFS序（in/out）              | 欧拉序                    |
| ------- | ------------------------- | ---------------------- |
| 记录位置    | 节点进入/离开时间                 | 整个路径节点顺序               |
| 每节点出现次数 | 1 次（进入）或 2 次（入 + 出）       | 通常 2 次                 |
| 数组长度    | `n` 或 `2n`                | `2n - 1`               |
| 用途      | 子树范围、树上前缀和、点修改            | 路径、LCA、RMQ             |
| 子树判断    | `in[v] ∈ [in[u], out[u])` | 通过 Euler 区间判断最小深度的 LCA |

## 例子：以如下树为例
```
       0
      / \
     1   2
        / \
       3   4
```
### DFS序记录（使用 in[u]）：
```
访问顺序：0 1 2 3 4
in[] =  [0, 1, 2, 3, 4]
out[] = [5, 2, 5, 4, 5]
子树 [2] 覆盖节点 2,3,4 的 in[v] ∈ [2, 5)

子树大小 = out[2] - in[2] = 5 - 2 = 3
```

### Euler 序列（每次回到父节点也记）：
```
euler = [0, 1, 0, 2, 3, 2, 4, 2, 0]
节点出现了多次，方便用 RMQ 求两个节点间最浅祖先

euler 数组长度 = 2n - 1 = 9
```

## 总结用法对比

| 应用           | 推荐序列                         |
| ------------ | ---------------------------- |
| 判断节点是否在某个子树中 | DFS序（in/out）                 |
| 统计子树和、修改节点值  | DFS序 + 树状数组或线段树              |
| 求两个点的 LCA    | 欧拉序 + RMQ                    |
| 路径问题（如路径上和）  | Euler Tour with Segment Tree |

在树的算法中，“欧拉序 (Euler Tour)” 和“DFS序 (DFS Order)” 是两种不同的遍历方式，虽然它们都基于深度优先搜索。它们的核心区别在于访问时机和记录内容不同，从而导致用途上的不同。

下面我们来分别解释它们，并比较区别。

一、DFS序（In-Time 和 Out-Time）

这是最常见的遍历方式，也称为入栈序（in-time）/ 出栈序（out-time）或者称为进入时间/离开时间。

cpp

int timer = 0;
void dfs(int u, int parent) {
    in[u] = timer++;
    for (int v : tree[u]) {
        if (v != parent) dfs(v, u);
    }
    out[u] = timer;
}

特点：

每个节点只记录一次进入（in[u]）和离开（out[u]）的时刻。

子树 u 的所有节点 v 满足：in[u] <= in[v] < out[u]

子树大小 = out[u] - in[u]

可以用来：

判定一个点是否在某个子树中（通过时间范围）

扁平化整棵树，便于做区间查询（如线段树、树状数组 (BIT)）

二、欧拉序（Euler Tour）

欧拉序是一种记录整条 DFS 遍历路径的方法。

cpp

vector<int> euler;

void euler_tour(int u, int parent) {
    euler.push_back(u);          // 第一次到达 u
    for (int v : tree[u]) {
        if (v != parent) {
            euler_tour(v, u);
            euler.push_back(u);  // 返回到 u 的时候再记一次
        }
    }
}

特点：

每个节点出现两次（进入、回溯）

整个 euler 数组长度是 2n - 1（对 n 个节点的树）

欧拉序对应的是“走过的路径”，适合做：

最近公共祖先 LCA 查询（RMQ）
处理“路径上”的问题

DFS序 vs 欧拉序：区别总结

特性	DFS序（in/out）	欧拉序
记录位置	节点进入/离开时间	整个路径节点顺序
每节点出现次数	1 次（进入）或 2 次（入 + 出）	通常 2 次
数组长度	`n` 或 `2n`	`2n - 1`
用途	子树范围、树上前缀和、点修改	路径、LCA、RMQ
子树判断	`in[v] ∈ [in[u], out[u])`	通过 Euler 区间判断最小深度的 LCA

例子：以如下树为例

DFS序记录（使用 in[u]）：

访问顺序：0 1 2 3 4
in[] =  [0, 1, 2, 3, 4]
out[] = [5, 2, 5, 4, 5]
子树 [2] 覆盖节点 2,3,4 的 in[v] ∈ [2, 5)

子树大小 = out[2] - in[2] = 5 - 2 = 3

Euler 序列（每次回到父节点也记）：

euler = [0, 1, 0, 2, 3, 2, 4, 2, 0]
节点出现了多次，方便用 RMQ 求两个节点间最浅祖先

euler 数组长度 = 2n - 1 = 9

总结用法对比

应用	推荐序列
判断节点是否在某个子树中	DFS序（in/out）
统计子树和、修改节点值	DFS序 + 树状数组或线段树
求两个点的 LCA	欧拉序 + RMQ
路径问题（如路径上和）	Euler Tour with Segment Tree

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

dfs序和欧拉序