侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【LCA, 递归】二叉树

GabrielxD
2023-03-13 / 0 评论 / 0 点赞 / 186 阅读 / 805 字
温馨提示:
本文最后更新于 2023-03-13,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

3555. 二叉树 - AcWing题库


给定一个 nn 个结点(编号 1n1 \sim n )构成的二叉树,其根结点为 11 号点。

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

树中所有边长均为 11

输入格式

第一行包含一个整数 TT ,表示共有 TT 组测试数据。

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

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

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

输出格式

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

数据范围

1T101 \le T \le 10 ,
1n,m10001 \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

思路

image-20230313173856560

如图( 绿 = + - 2 * ),在二叉树中,对于任何两个节点 a,ba, b ,有:d(a,b)=h(a)+h(b)2h(LCA(a,b))d(a, b) = h(a) + h(b) - 2h(\text{LCA}(a, b)) ,其中:dd 指树上两点之间的距离, hh 指一个节点到根节点之间的距离,LCA(a,b)\text{LCA}(a, b) 表示 a,ba, 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]);
            }
        }
    }
}

0

评论区