GESP六级通关秘籍：树的遍历

树的遍历是解决很多问题的核心算法。以下是一些常见的问题类型，以及对应的洛谷题目编号：

1.树的深度/高度计算：通过遍历可以计算树的深度或高度。 P1087 [FBI树]（虽然不是直接求深度，但需要遍历）

2.子树大小（节点数）计算：通过遍历可以统计每个节点的子树大小。 P1120 小木棍（非树，但类似思想）或P3379 [模板]最近公共祖先（LCA）（需要子树大小）

3.最近公共祖先（LCA）：通过遍历（如DFS）可以预处理节点深度，进而求LCA。 P3379 【模板】最近公共祖先（LCA）

4.树的重心：通过遍历可以找到树的重心。 P1364 医院设置（求带权树的重心）或P1395 会议（树的重心）

5.树的直径：通过两次DFS或BFS可以求出树的直径。 B4016 树的直径 P3304 [SDOI2013]直径 或 P1099 树网的核（与直径相关）

6.树形动态规划（树形DP）：在树上进行动态规划，通常需要遍历树。 P1352 没有上司的舞会（经典树形DP）

7.欧拉序与RMQ问题：通过DFS序可以将树转化为序列问题。 P3379 【模板】最近公共祖先（LCA）（也可以用欧拉序求LCA）

8.判断树的结构（同构等）：通过遍历可以获取树的结构信息。 P5018 [NOIP2018 普及组] 对称二叉树（需要遍历判断）

9.路径问题：通过遍历可以处理树上路径的查询和修改。 P3384 【模板】树链剖分（路径修改与查询）

10.子树问题：通过DFS序可以将子树转化为区间问题。 P3384 【模板】树链剖分（子树修改与查询）