【LCA, 递归】二叉树

题目

3555. 二叉树 - AcWing题库

---

给定一个 $n$ 个结点（编号 $1 \sim n$ ）构成的二叉树，其根结点为 $1$ 号点。

进行 $m$ 次询问，每次询问两个结点之间的最短路径长度。

树中所有边长均为 $1$ 。

输入格式

第一行包含一个整数 $T$ ，表示共有 $T$ 组测试数据。

每组数据第一行包含两个整数 $n,m$ 。

接下来 $n$ 行，每行包含两个整数，其中第 $i$ 行的整数表示结点 $i$ 的子结点编号。如果没有子结点则输出 $-1$ 。

接下来 $m$ 行，每行包含两个整数，表示要询问的两个结点的编号。

输出格式

每组测试数据输出 $m$ 行，代表查询的两个结点之间的最短路径长度。

数据范围

$1 \le T \le 10$ ,
$1 \le n,m \le 1000$

输入样例：

1
8 4
2 3
4 5
6 -1
-1 -1
-1 7
-1 -1
8 -1
-1 -1
1 6
4 6
4 5
8 1

输出样例：

2
4
2
4

解题

方法一：LCA

思路

如图（ 绿 = 橙 + 蓝 - 2 * 红 ），在二叉树中，对于任何两个节点 $a, b$ ，有：$d(a, b) = h(a) + h(b) - 2h(\text{LCA}(a, b))$ ，其中：$d$ 指树上两点之间的距离， $h$ 指一个节点到根节点之间的距离，$\text{LCA}(a, b)$ 表示 $a, b$ 两点的最近公共祖先。

所以只要能求出两点的最近公共祖先就能求出它俩之间的最短路径长度，本题数据范围比较小，可以直接暴力（爬山法）求 LCA ，具体来说：

• 首先把两个节点中较低的爬升至与较高节点一样的高度。
• 当两节点高度相同时，同时爬升两个点。
  • 知道两节点是同一个节点时，就找到了最近公共祖先节点。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 1010;
    static int[] l = new int[N], r = new int[N], p = new int[N];
    static int[] dep = new int[N];
    
    static void dfs(int u, int d) {
        dep[u] = d;
        if (l[u] != -1) dfs(l[u], d + 1);
        if (r[u] != -1) dfs(r[u], d + 1);
    }
    
    static int getLca(int a, int b) {
        if (dep[a] > dep[b]) {
            int t = a;
            a = b;
            b = t;
        }
        while (dep[b] != dep[a]) b = p[b];
        while (a != b) {
            a = p[a];
            b = p[b];
        }
        return a;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int t = (int) in.nval;
        while (t-- > 0) {
            in.nextToken();
            int n = (int) in.nval;
            in.nextToken();
            int m = (int) in.nval;
            Arrays.fill(l, -1);
            Arrays.fill(r, -1);
            for (int u = 1; u <= n; ++u) {
                in.nextToken();
                int a = (int) in.nval;
                in.nextToken();
                int b = (int) in.nval;
                l[u] = a;
                r[u] = b;
                if (a != -1) p[a] = u;
                if (b != -1) p[b] = u;
            }
            dfs(1, 0);
            while (m-- > 0) {
                in.nextToken();
                int a = (int) in.nval;
                in.nextToken();
                int b = (int) in.nval;
                int lca = getLca(a, b);
                System.out.println(dep[a] + dep[b] - 2 * dep[lca]);
            }
        }
    }
}