题目描述
leetcode 困难题
给你一个整数 n ，表示你有一棵含有 2n - 1 个节点的 完全二叉树 。根节点的编号是 1 ，树中编号在[1, 2n - 1 - 1] 之间，编号为 val 的节点都有两个子节点，满足：
- 左子节点的编号为 2 * val
- 右子节点的编号为 2 * val + 1
给你一个长度为 m 的查询数组 queries ，它是一个二维整数数组，其中 queries[i] = [ai, bi] 。对于每个查询，求出以下问题的解：
- 在节点编号为 ai 和 bi 之间添加一条边。
- 求出图中环的长度。
- 删除节点编号为 ai 和 bi 之间新添加的边。
注意：
- 环 是开始和结束于同一节点的一条路径，路径中每条边都只会被访问一次。
- 环的长度是环中边的数目。
- 在树中添加额外的边后，两个点之间可能会有多条边。
请你返回一个长度为 m 的数组 answer ，其中 answer[i] 是第 i 个查询的结果。
示例1：
1
2
3
4
5
6
| 输入：n = 3, queries = [[5,3],[4,7],[2,3]]
输出：[4,5,3]
解释：上图是一棵有 23 - 1 个节点的树。红色节点表示添加额外边后形成环的节点。
- 在节点 3 和节点 5 之间添加边后，环为 [5,2,1,3] ，所以第一个查询的结果是 4 。删掉添加的边后处理下一个查询。
- 在节点 4 和节点 7 之间添加边后，环为 [4,2,1,3,7] ，所以第二个查询的结果是 5 。删掉添加的边后处理下一个查询。
- 在节点 2 和节点 3 之间添加边后，环为 [2,1,3] ，所以第三个查询的结果是 3 。删掉添加的边。
|
提示1：
1
2
3
4
5
6
| 2 <= n <= 30
m == queries.length
1 <= m <= 10^5
queries[i].length == 2
1 <= ai, bi <= 2n - 1
ai != bi
|
最近公共祖先（LCA）
实际为最近公共祖先问题，环的长度显然为结点 $a$ 和 $b$ 分别到 $LCA$ 的距离之和再加上 $1$。
求 $LCA$ 的一种朴素解法为
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int[] cycleLengthQueries(int n, int[][] queries) {
int m = queries.length;
int[] ans = new int[m];
for(int i = 0; i < m; i++){
int a = queries[i][0];
int b = queries[i][1];
int cur = 1;
while(a != b){
if(a > b){
a /= 2;
}else{
b /= 2;
}
cur++;
}
ans[i] = cur;
}
return ans;
}
}
|
转二进制
由于是满二叉树，并且结点编号符合题目中的规则，所以某个结点值的二进制值为从根节点到该结点的路径，其中 $0$ 表示左结点， $1$ 表示右结点或者根结点。例如 $5$ 为 $101$：$根结点->左结点->右结点$。
设某个结点 $x$ 到根结点的距离为 $d_x$，可以得到 $ans_i = d_{a_i} + d_{b_i} - (2 \times d_{LCA}) + 1$ ，其中 $d_{a_i}$ 和 $d_{b_i}$ 分别为两个结点的二进制值长度，而 $d_{LCA}$ 显然为两个结点的二进制值从根节点开始到第一个不同的二进制位的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int[] cycleLengthQueries(int n, int[][] queries) {
int m = queries.length;
int[] ans = new int[m];
for (int i = 0; i < m; i++) {
String a = Integer.toBinaryString(queries[i][0]);
String b = Integer.toBinaryString(queries[i][1]);
int j = 0;
for (; j < a.length() && j < b.length(); j++) {
if (a.charAt(j) != b.charAt(j))
break;
}
ans[i] = a.length() + b.length() - 2 * j + 1;
}
return ans;
}
}
|