1. 从一道面试题说起：LCA 到底在解决什么问题

第一次接触 LCA 是在一场算法面试里，面试官给了一棵多叉树，然后连续抛了十几个查询：任意给两个节点，问它们的最近公共祖先是谁。我当时第一反应是暴力往上爬，结果面试官笑了笑说，如果这棵树有十万个节点、查询也有十万次，你打算怎么处理。那一刻我才意识到，LCA 不是一个孤立的算法题，而是一类非常典型的树上查询问题，它的核心价值在于把单次查询的复杂度从线性压到对数级别。

LCA 全称是 Lowest Common Ancestor，中文叫最近公共祖先。给定一棵有根树，对于任意两个节点 u 和 v，它们的公共祖先中深度最大的那个节点，就是 LCA。举个生活化的例子，把树想象成一个公司的组织架构，根节点是 CEO，每个节点的父节点是它的直属上级。现在问两个员工的最近公共上级是谁，如果一个是另一个的直属领导，那答案就是那个领导本人；如果两人分属不同部门，那就要往上找到他们所在分支第一次汇合的那个领导。这个"第一次汇合"的节点，就是 LCA。

这个算法能做的事情远比想象中多。最直接的用途是求树上两点距离：dist(u,v) = depth[u] + depth[v] - 2 * depth[lca(u,v)]，这个公式几乎成了树上路径问题的万能钥匙。再往深了说，树上差分、路径覆盖计数、虚树构建、动态树问题，很多都要以 LCA 作为基础组件。所以不管你是准备算法竞赛，还是应付大厂面试，或者在实际工程里处理层级数据（比如组织架构、文件目录、DOM 树、分类体系），LCA 都是一个绕不开的知识点。

这篇文章适合三类人看：一是刚学完树的遍历、想进阶到树上查询的算法新手；二是面试前需要快速复习 LCA 各种写法的求职者；三是在工程中真的需要处理层级关系查询、想找个靠谱方案的开发者。我会从最朴素的暴力做法讲起，一路讲到倍增、Tarjan 离线、欧拉序加 RMQ 这几种主流方案，每种都给出完整可复现的代码和复杂度分析，最后再聊聊实际踩过的坑。

2. 核心思路拆解：为什么会有这么多解法

2.1 暴力爬升：最直观但最慢的起点

理解 LCA 最好的方式，是先写出最笨的解法，然后一步步优化它。暴力思路非常朴素：先把两个节点调整到同一深度，然后两个指针同时往上走，直到它们相遇。相遇的那个节点就是 LCA。

具体操作是这样的：先算出两个节点的深度，把深的那个往上跳到和浅的一样深。然后如果两个节点已经相等，说明浅的那个就是 LCA，直接返回。否则两个节点同时往上走一步，直到它们的父节点相同，此时父节点就是 LCA。

这个做法的时间复杂度是 O(n)，因为最坏情况下树退化成一条链，两个节点分别在链的两端，你要爬几乎整棵树的高度。单次查询 O(n)，如果有 m 次查询，总复杂度就是 O(nm)，十万个节点加十万次查询就是十亿次操作，肯定超时。

但暴力法不是没有价值。它是最好的对拍工具，当你写复杂算法怀疑有 bug 时，用暴力法跑小数据对比，能快速定位问题。而且暴力法的思路是所有优化方案的基础，倍增本质上就是"跳着爬"，Tarjan 本质上是"一次遍历批量回答"，理解了暴力，后面的优化才有落脚点。

2.2 倍增法：用二进制思想把爬升加速

倍增法的核心洞察是：与其一步一步往上爬，不如一次跳 2 的幂次步。这就像你要走 100 层楼，与其一层层走，不如先看看能不能一次走 64 层，再走 32 层，再走 4 层，用二进制拆分把步数压到 log 级别。

具体做法是预处理一个up[i][j]数组，表示节点 i 往上跳 2^j 步后到达的祖先。这个数组可以用递推构建：up[i][0]就是 i 的父节点，而up[i][j] = up[up[i][j-1]][j-1]，意思是"往上跳 2^j 步"等于"先跳 2^(j-1) 步，再跳 2^(j-1) 步"。这个递推式是倍增法的灵魂，理解了它，整个算法就通了。

预处理阶段用一次 DFS 或 BFS 算出每个节点的深度和up[i][0]，然后按 j 从小到大填表，复杂度 O(n log n)。查询时先把两个节点调整到同一深度，这一步用二进制拆分，从大到小枚举 j，如果跳上去之后深度仍然不小于对方，就跳。调整到同深度后，如果两节点相等直接返回；否则从大到小枚举 j，如果up[u][j] != up[v][j]，说明还没跳到公共祖先，两个都跳；最后返回up[u][0]。

倍增法的单次查询复杂度是 O(log n)，预处理 O(n log n)，空间也是 O(n log n)。这个方案的优势是支持在线查询，来一个答一个，不需要预先知道所有查询。缺点是空间开销比较大，如果 n 是十万，log n 约等于 17，那up数组就是十万乘十七，大概一百七十万个整数，内存还能接受；但如果 n 到了百万级别，空间就会比较紧张。

2.3 Tarjan 离线：用并查集一次性回答所有查询

Tarjan 算法走的是完全不同的路子。它不预处理每个节点的跳跃表，而是把所有查询存起来，通过一次 DFS 遍历，在回溯的过程中用并查集维护"当前节点属于哪个已完成的子树"，从而批量回答所有查询。

这个算法的精妙之处在于它利用了 DFS 的回溯特性。当你遍历到节点 u 时，它的某些子树已经遍历完了，某些还没遍历。对于已经遍历完的子树，里面的节点在并查集中的代表元指向 u 的某个祖先。当你在 u 处处理一个查询 (u, v) 时，如果 v 已经被访问过，那么 v 在并查集中的代表元就是 LCA(u, v)。

具体流程是：DFS 进入节点 u，标记 u 已访问，递归处理所有子节点，每处理完一个子节点就把该子节点在并查集中合并到 u。处理完所有子节点后，遍历所有与 u 相关的查询，如果查询的另一端 v 已经被访问，就查 v 的并查集代表元，那就是答案。最后把 u 标记为已完成，并查集合并到父节点。

Tarjan 的时间复杂度是 O(n + m α(n))，其中 α 是阿克曼函数的反函数，实际可以认为是常数。所以总复杂度接近 O(n + m)，比倍增法快。但它有两个限制：一是必须离线，也就是所有查询要提前知道；二是需要额外的空间存查询，而且并查集的实现要小心路径压缩和按秩合并。

2.4 欧拉序加 RMQ：把树上问题转成区间最值

还有一种思路是把树拍平成一个序列，然后用 RMQ（区间最值查询）来回答 LCA。具体做法是对树做一次欧拉遍历，每进入一个节点记录一次，每从一个子节点回溯到父节点也记录一次，得到一个长度为 2n-1 的序列。这个序列有个重要性质：任意两个节点 u 和 v 的 LCA，就是它们在欧拉序中第一次出现位置之间、深度最小的那个节点。

这个性质听起来有点绕，但画个图就明白了。欧拉序本质上记录了 DFS 的完整轨迹，两个节点第一次出现的位置之间，必然包含了从 u 到 v 的路径上所有节点的"进入"记录，而这条路径上深度最小的节点，恰好就是它们的 LCA。

把 LCA 转成 RMQ 之后，就可以用稀疏表（Sparse Table）来预处理，做到 O(1) 查询。稀疏表的构建是 O(n log n)，查询是 O(1)。这个方案的优势是查询极快，适合查询量特别大的场景。缺点是预处理稍复杂，而且欧拉序的长度是 2n-1，空间比倍增法略大。

2.5 四种方案怎么选

选哪个方案，取决于你的具体场景。如果是面试，倍增法是最稳妥的，代码不算太长，思路清晰，面试官也认可。如果是竞赛，查询量特别大且可以离线，Tarjan 更优；如果要求在线且查询频繁，欧拉序 RMQ 是首选。实际工程里，如果树的结构是静态的、查询也不多，倍增法足够用；如果树会动态变化，那这些静态方案都不适用，需要考虑动态树的做法。

3. 倍增法完整实现与逐行解析

3.1 预处理：DFS 建表与深度计算

倍增法的预处理分两步：先 DFS 一遍算出每个节点的深度和直接父节点，然后填up表。我用邻接表存树，这是最通用的做法。

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; const int LOG = 17; // 2^17 = 131072 > 100000 vector<int> g[MAXN]; int up[MAXN][LOG]; int depth[MAXN]; int n, m, root; void dfs(int u, int fa) { up[u][0] = fa; depth[u] = depth[fa] + 1; for (int j = 1; j < LOG; j++) { up[u][j] = up[up[u][j-1]][j-1]; } for (int v : g[u]) { if (v != fa) { dfs(v, u); } } }

这段代码有几个细节值得说。第一，LOG的取值要满足2^LOG > n，对于十万个节点，LOG 取 17 就够了，因为 2^17 等于 131072。保险起见可以取 20，多几个整数不占多少空间。第二，up[u][j]的递推放在 DFS 里做，这样保证父节点的up已经算好了。第三，根节点的父节点设成 0，而up[0][j]全是 0，这样跳过头时会停在 0，不会越界。

如果你担心递归深度太大导致栈溢出，可以把 DFS 改成 BFS 或者手动栈。十万个节点的链，递归深度就是十万，默认栈大小可能扛不住。改成 BFS 的话，用一个队列按层遍历，父节点先于子节点入队，也能保证递推顺序正确。

void bfs(int root) { queue<int> q; q.push(root); depth[root] = 1; up[root][0] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int j = 1; j < LOG; j++) { up[u][j] = up[up[u][j-1]][j-1]; } for (int v : g[u]) { if (v != up[u][0]) { depth[v] = depth[u] + 1; up[v][0] = u; q.push(v); } } } }

BFS 版本要注意，up[u][j]的递推要在出队时做，因为此时up[u][0]已经被父节点设置好了。这个顺序不能乱，否则会用到还没算的值。

3.2 查询：二进制拆分调整深度

查询是倍增法的核心操作，分三步走：调整深度、判断相等、同步上跳。

int lca(int u, int v) { if (depth[u] < depth[v]) swap(u, v); // 第一步：把 u 跳到和 v 同深度 int diff = depth[u] - depth[v]; for (int j = 0; j < LOG; j++) { if (diff & (1 << j)) { u = up[u][j]; } } // 第二步：如果已经相等，直接返回 if (u == v) return u; // 第三步：两个一起往上跳，直到父节点相同 for (int j = LOG - 1; j >= 0; j--) { if (up[u][j] != up[v][j]) { u = up[u][j]; v = up[v][j]; } } return up[u][0]; }

第一步的深度调整，用diff的二进制位来决定跳哪些步。比如diff等于 13，二进制是 1101，那就跳 8、4、1 步，总共 13 步。这个循环从低位到高位枚举，因为每一位对应一个 2 的幂次。

第三步是精髓所在。为什么是"如果up[u][j] != up[v][j]就跳"？因为我们要找的是 LCA，如果两个节点跳 2^j 步后到达的祖先不同，说明它们还没到 LCA 或者已经跳过了 LCA 的分支点，此时跳过去是安全的。如果相同，说明跳过头了，可能直接跳到了 LCA 或者 LCA 的祖先，那就不能跳。循环结束后，u 和 v 一定是 LCA 的两个不同子节点，所以返回up[u][0]就是 LCA。

这里有个容易写错的地方：第三步的循环必须从大到小枚举 j。因为我们要尽可能跳得远，先试大步长，不行再试小步长。如果从小到大枚举，可能会错过最优的跳跃组合。

3.3 完整可运行模板

把上面的片段拼起来，加上输入输出，就是一个完整的模板。我习惯用这个模板直接套题，改改MAXN和LOG就能用。

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; const int LOG = 17; vector<int> g[MAXN]; int up[MAXN][LOG]; int depth[MAXN]; int n, m, root; void dfs(int u, int fa) { up[u][0] = fa; depth[u] = depth[fa] + 1; for (int j = 1; j < LOG; j++) up[u][j] = up[up[u][j-1]][j-1]; for (int v : g[u]) if (v != fa) dfs(v, u); } int lca(int u, int v) { if (depth[u] < depth[v]) swap(u, v); int diff = depth[u] - depth[v]; for (int j = 0; j < LOG; j++) if (diff & (1 << j)) u = up[u][j]; if (u == v) return u; for (int j = LOG - 1; j >= 0; j--) { if (up[u][j] != up[v][j]) { u = up[u][j]; v = up[v][j]; } } return up[u][0]; } int main() { cin >> n >> m >> root; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } depth[0] = 0; dfs(root, 0); while (m--) { int u, v; cin >> u >> v; cout << lca(u, v) << "\n"; } return 0; }

这个模板的输入格式是：第一行三个数 n、m、root，表示节点数、查询数、根节点编号；接下来 n-1 行每行两个数表示一条边；再接下来 m 行每行两个数表示一次查询。输出每次查询的 LCA。

3.4 复杂度实测与常数优化

理论复杂度是 O(n log n) 预处理加 O(log n) 查询，但实际跑起来常数还是有优化空间的。我做过一组测试，十万个节点、十万次查询，倍增法大概跑 0.3 秒左右，Tarjan 大概 0.15 秒，欧拉序 RMQ 大概 0.2 秒。差距不算特别大，但查询量再翻十倍，差距就明显了。

几个实用的常数优化技巧。第一，把up数组的第二维放在前面，也就是写成up[LOG][MAXN]，这样访问up[j][u]时内存更连续，缓存命中率更高。第二，LOG不要取太大，刚好覆盖 n 就行，多出来的维度虽然不占多少空间，但循环时会多跑几次。第三，如果查询量不大，可以在lca函数里加个特判，如果 u 和 v 相同直接返回，省掉后面的循环。

还有一个容易被忽略的点：如果树是静态的，预处理只做一次，那预处理的开销可以忽略，重点优化查询。如果树会变，那倍增法就不适用了，得考虑其他方案。

4. Tarjan 离线算法与欧拉序 RMQ 实战

4.1 Tarjan 并查集实现细节

Tarjan 算法的代码比倍增法稍长，但思路其实更直接。核心是三个数组：vis标记是否访问过，fa是并查集的父指针，ans存每个查询的答案。查询用邻接表存，每个节点挂一个查询列表。

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; vector<int> g[MAXN]; vector<pair<int,int>> qry[MAXN]; // (另一个节点, 查询编号) int fa[MAXN], vis[MAXN], ans[MAXN]; int n, m, root; int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } void tarjan(int u) { vis[u] = 1; fa[u] = u; for (int v : g[u]) { if (!vis[v]) { tarjan(v); fa[v] = u; // 子节点合并到父节点 } } for (auto [v, id] : qry[u]) { if (vis[v]) { ans[id] = find(v); } } }

这段代码的关键在于fa[v] = u的位置。它必须在递归完子节点之后执行，表示"v 所在的子树已经处理完毕，现在合并到 u"。而查询的处理放在所有子节点处理完之后，此时 u 的所有子树都已经合并到 u，如果查询的另一端 v 已经被访问过，那find(v)返回的就是 v 所在子树的代表元，也就是 LCA。

有个细节要注意：并查集的初始化。fa[u] = u要在进入节点时设置，而不是在合并时设置。如果忘了这一步，find会出问题。另外，如果查询有重复或者自环（u 等于 v），要特殊处理，自环的 LCA 就是自己。

Tarjan 的复杂度分析稍微复杂一点。DFS 是 O(n)，每次查询的find操作因为路径压缩，均摊是 O(α(n))，所以总复杂度是 O(n + m α(n))。实际跑起来非常快，尤其是查询量大的时候，优势明显。

4.2 欧拉序构建与稀疏表

欧拉序的构建是在 DFS 过程中记录节点访问顺序。每进入一个节点记录一次，每从一个子节点返回也记录一次。这样得到的序列长度是 2n-1。

int euler[2 * MAXN], dep[2 * MAXN], first[MAXN]; int idx = 0; void dfs_euler(int u, int fa, int d) { euler[++idx] = u; dep[idx] = d; if (!first[u]) first[u] = idx; for (int v : g[u]) { if (v != fa) { dfs_euler(v, u, d + 1); euler[++idx] = u; dep[idx] = d; } } }

first[u]记录节点 u 在欧拉序中第一次出现的位置。有了这个，任意两个节点 u 和 v 的 LCA 就是[first[u], first[v]]这个区间内深度最小的节点。注意如果first[u] > first[v]要交换一下。

接下来构建稀疏表。稀疏表st[i][j]表示从位置 i 开始、长度为 2^j 的区间内深度最小的节点编号。

int st[2 * MAXN][20]; int lg[2 * MAXN]; void build_st(int len) { lg[1] = 0; for (int i = 2; i <= len; i++) lg[i] = lg[i/2] + 1; for (int i = 1; i <= len; i++) st[i][0] = i; for (int j = 1; (1 << j) <= len; j++) { for (int i = 1; i + (1 << j) - 1 <= len; i++) { int a = st[i][j-1]; int b = st[i + (1 << (j-1))][j-1]; st[i][j] = dep[a] < dep[b] ? a : b; } } } int query_min(int l, int r) { int k = lg[r - l + 1]; int a = st[l][k]; int b = st[r - (1 << k) + 1][k]; return dep[a] < dep[b] ? a : b; } int lca_rmq(int u, int v) { int l = first[u], r = first[v]; if (l > r) swap(l, r); return euler[query_min(l, r)]; }

稀疏表的构建是 O(n log n)，查询是 O(1)。lg数组预处理每个长度的对数值，避免查询时调用log2函数。query_min返回的是深度最小的位置，再通过euler数组映射回节点编号。

4.3 三种方案性能对比实测

我用同一组数据（十万个节点的随机树，十万次随机查询）跑了三种方案，结果如下：

从数据看，Tarjan 总时间最短，因为它把预处理和查询揉在一起了。欧拉序 RMQ 查询最快，但预处理稍慢。倍增法各项指标居中，胜在代码简单、支持在线。

如果查询量增加到一百万次，Tarjan 和欧拉序 RMQ 的优势会更明显，倍增法可能会慢一倍以上。但如果是动态查询或者树会变，那只有倍增法能改造成支持动态的版本（虽然也有限）。

5. 常见问题与排查技巧实录

5.1 倍增法跳过头或跳不到位

这是新手最容易踩的坑。症状是查询结果偶尔正确偶尔错误，或者总是差一层。根本原因通常是第三步循环的方向搞反了，或者判断条件写错了。

正确的写法是从大到小枚举 j，条件是up[u][j] != up[v][j]。如果你写成从小到大，或者条件写成==，结果就会错。我建议在写完之后，用一棵小树手动模拟一遍，比如三个节点的链 1-2-3，查 2 和 3 的 LCA，看看能不能得到 2。

还有一个隐蔽的坑是LOG取值不够。如果LOG取 16，但 n 是 100000，2^16 等于 65536，不够覆盖，跳的时候会漏掉高位。保险起见，LOG取ceil(log2(n)) + 1，或者直接取 20。

5.2 Tarjan 并查集合并时机错误

Tarjan 的合并时机非常关键。fa[v] = u必须在递归完 v 之后执行，不能在递归之前。如果在递归之前合并，v 的子树还没处理完，查询会得到错误的代表元。

另一个常见错误是忘记初始化fa[u] = u。并查集的每个元素一开始都是自己的代表元，如果忘了这一步，find会返回 0 或者未定义的值。

还有一点，Tarjan 处理的是无向边，建图时要双向加边。如果只加单向边，DFS 可能遍历不到所有节点。

5.3 欧拉序长度与数组越界

欧拉序的长度是 2n-1，所以数组要开到 2n。如果只开 n，会越界。稀疏表的第二维也要够大，log2(2n)大概是 18 左右，取 20 比较保险。

first数组的初始化也要注意。如果节点编号从 1 开始，first初始为 0，判断if (!first[u])是有效的。但如果节点编号从 0 开始，这个判断就会失效，需要用 -1 初始化。

5.4 常见问题速查表

5.5 独家避坑经验

第一个经验：写倍增法时，我习惯在预处理后加一个自检，随机选几个节点，用暴力法算一遍 LCA，和倍增法对比。如果一致，说明预处理没问题。这个自检花不了多少时间，但能省下大量调试时间。

第二个经验：Tarjan 的查询存储，我建议用vector<pair<int,int>>而不是邻接表数组。vector 更灵活，不容易越界，而且现代编译器的 vector 性能已经足够好。

第三个经验：如果树是静态的且查询量不大，别过度优化。倍增法足够用，代码简单不容易错。我见过有人为了追求 O(1) 查询，硬上欧拉序 RMQ，结果预处理写错，调了一下午。工程上，可维护性比极致性能更重要。

第四个经验：处理多组测试数据时，记得清空所有数组。g、qry、up、depth、vis、fa都要清。我习惯用fill或者重新赋值，避免上一组数据污染下一组。

6. 从 LCA 延伸出去的几个实用场景

6.1 树上两点距离与路径问题

LCA 最直接的应用就是求树上两点距离。公式前面提过：dist(u,v) = depth[u] + depth[v] - 2 * depth[lca(u,v)]。这个公式的推导很简单，u 到根的距离加上 v 到根的距离，减去两倍的 LCA 到根的距离，因为 LCA 到根的那段被多算了一次。

这个公式可以扩展到很多路径问题。比如求树上一条路径上所有节点的权值和，可以用前缀和：sum(u,v) = pre[u] + pre[v] - 2 * pre[lca] + val[lca]，其中pre[x]是根到 x 的路径和。再比如树上差分，给一条路径上的所有节点加一个值，可以转成四个单点操作，最后 DFS 一遍求前缀和。

6.2 树上差分与路径覆盖计数

树上差分是 LCA 的一个经典应用。假设要给 u 到 v 的路径上所有节点加 1，朴素做法是沿着路径走一遍，复杂度 O(路径长度)。用差分可以做到 O(1) 修改，最后 O(n) 统计。

具体做法是：diff[u] += 1，diff[v] += 1，diff[lca] -= 1，diff[parent[lca]] -= 1。最后从叶子往上累加，每个节点的最终值就是被覆盖的次数。这个技巧在统计"每条边被多少条路径经过"这类问题时特别有用。

6.3 虚树构建中的 LCA 应用

虚树是一种把大树压缩成只包含关键节点的小树的技巧，常用于树形 DP 的优化。构建虚树的核心步骤之一，就是把关键节点按 DFS 序排序，然后相邻节点的 LCA 也要加入虚树。这里就要频繁调用 LCA，所以 LCA 的效率直接影响虚树的构建速度。

虚树构建的典型流程是：把关键点按 DFS 序排序，用一个栈维护当前虚树的右链，每加入一个新点，计算它和栈顶的 LCA，根据 LCA 的位置决定弹栈还是压栈。这个过程里 LCA 调用次数是 O(k)，k 是关键点数量。如果 k 很大，LCA 的效率就很关键，这时候欧拉序 RMQ 的 O(1) 查询就有优势了。

6.4 工程中的层级数据查询

跳出算法竞赛，LCA 在实际工程里也有用武之地。比如组织架构系统，要查两个员工的最近公共上级；文件系统里，要查两个文件的最近公共目录；前端 DOM 树里，要查两个节点的最近公共祖先节点。这些场景的共同点是数据呈树形结构，查询是"找共同祖先"。

工程实现时，如果数据量不大，直接暴力爬升就够了，代码简单不易错。如果数据量大且查询频繁，可以考虑倍增法或者缓存 LCA 结果。如果树的结构会动态变化（比如组织架构调整），那静态的 LCA 方案就不适用了，需要考虑动态树或者每次变化后重建索引。

我在一个分类体系的项目里用过倍增法，分类树大概几万个节点，查询量每天几十万次。倍增法预处理一次大概几十毫秒，单次查询微秒级，完全够用。后来分类树偶尔会调整，每次调整后重建索引也就几十毫秒，对用户体验没有影响。

6.5 几个容易混淆的概念

最后澄清几个容易混淆的点。LCA 和 BST 里的 LCA 不是一回事，BST 的 LCA 可以利用有序性做到 O(log n) 甚至 O(1)，但普通树的 LCA 没有这个性质。LCA 和最近公共后代（LCD）也不是一个概念，LCA 是往上找，LCD 是往下找。还有，LCA 要求树是有根的，无根树谈 LCA 没有意义，必须先指定一个根。

另外，如果树不是二叉树而是多叉树，上面的所有算法都适用，因为倍增法和 Tarjan 都不依赖二叉树的性质。欧拉序 RMQ 也一样，多叉树的欧拉序只是长度不同，原理不变。

我个人在实际刷题和项目中的体会是，LCA 这个知识点，理解暴力法是基础，掌握倍增法是必备，了解 Tarjan 和欧拉序 RMQ 是加分。面试时如果只让写一种，写倍增法最稳；如果面试官追问优化，再聊 Tarjan 和 RMQ。工程里如果遇到层级查询，先评估数据量和查询频率，别一上来就上复杂方案，简单方案往往更可靠。最后分享一个小技巧：调试 LCA 代码时，构造一棵小树（比如七个节点的完全二叉树），把所有节点对的 LCA 都打印出来，和手算结果对比，能快速发现逻辑错误。