题目描述
给定一个 n 个结点(编号 1∼n)构成的二叉树,其根结点为 1 号点。
进行 m 次询问,每次询问两个结点之间的最短路径长度。
算法1
(深度优先遍历DFS)
存储每个点的左右子节点以及父节点,每个结点都存储对应的深度(depth)
从1号结点(根节点)进行DFS,计算每个点的深度
找到两结点的第一个公共父节点,最后计算距离
时间复杂度 $O(n^2)$
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
const int N = 1010;
int T, n, m;
int l[N], r[N], fa[N], depth[N];
void dfs(int root) {
if (l[root]) depth[l[root]] = depth[root] + 1, dfs(l[root]);
if (r[root]) depth[r[root]] = depth[root] + 1, dfs(r[root]);
}
int main() {
scanf("%d", &T);
while (T -- ) {
memset(l, 0, sizeof l);
memset(r, 0, sizeof r);
memset(fa, 0, sizeof fa);
memset(depth, 0, sizeof depth);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) {
int lc, rc;
scanf("%d%d", &lc, &rc);
if (~lc) l[i] = lc, fa[lc] = i;
if (~rc) r[i] = rc, fa[rc] = i;
}
depth[1] = 1;
dfs(1);
while (m -- ) {
int a, b, af, bf;
scanf("%d%d", &a, &b);
if (depth[a] > depth[b]) swap(a, b);
af = a, bf = b;
while (depth[af] != depth[bf]) bf = fa[bf];
while (af != bf) {
if (fa[af]) af = fa[af];
if (fa[bf]) bf = fa[bf];
}
printf("%d\n", depth[a] - depth[af] + depth[b] - depth[bf]);
}
}
return 0;
}