LeetCode 题解工作台
查询树中环的长度
给你一个整数 n ，表示你有一棵含有 2 n - 1 个节点的 完全二叉树 。根节点的编号是 1 ，树中编号在 [1, 2 n - 1 - 1] 之间，编号为 val 的节点都有两个子节点，满足： 左子节点的编号为 2 * val 右子节点的编号为 2 * val + 1 给你一个长度为 m 的查询…
3
题型
4
代码语言
3
相关题
当前训练重点
困难 · 二分·树·traversal
答案摘要
对于每次查询，我们找出 , 两个节点的最近公共祖先，并且记录向上走的步数，那么此次查询的答案就是步数加一。 求最近公共祖先时，如果 $a \gt b$，那么我们将 往父节点移动；如果 $a \lt b$，我们将 往其父节点移动。过程中累计步数，直至 $a = b$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一个整数 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：
输入：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 。删掉添加的边。
示例 2：
输入：n = 2, queries = [[1,2]] 输出：[2] 解释：上图是一棵有 22 - 1 个节点的树。红色节点表示添加额外边后形成环的节点。 - 在节点 1 和节点 2 之间添加边后，环为 [2,1] ，所以第一个查询的结果是 2 。删掉添加的边。
提示：
2 <= n <= 30m == queries.length1 <= m <= 105queries[i].length == 21 <= ai, bi <= 2n - 1ai != bi
解题思路
方法一：求最近公共祖先
对于每次查询，我们找出 , 两个节点的最近公共祖先，并且记录向上走的步数，那么此次查询的答案就是步数加一。
求最近公共祖先时，如果 ，那么我们将 往父节点移动；如果 ，我们将 往其父节点移动。过程中累计步数，直至 。
时间复杂度 。其中 为数组 queries 的长度。
class Solution:
def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:
ans = []
for a, b in queries:
t = 1
while a != b:
if a > b:
a >>= 1
else:
b >>= 1
t += 1
ans.append(t)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for an understanding of tree traversal and cycle detection techniques.
- question_mark
Assess the ability to apply Union-Find for dynamic connectivity management.
- question_mark
Evaluate the candidate's approach to handling edge cases like tree structure updates after each query.
常见陷阱
外企场景- error
Failure to manage dynamic tree structure efficiently leads to poor performance.
- error
Not accounting for the removal of the edge after each query could result in incorrect results.
- error
Inefficient cycle detection can lead to excessive computation time, especially for large inputs.
进阶变体
外企场景- arrow_right_alt
Modify the problem to consider non-binary trees.
- arrow_right_alt
Handle a scenario where queries are static and no edges are removed between queries.
- arrow_right_alt
Optimize for scenarios with large `n` and more queries.