Hard

题目描述

给你一个整数 n。存在一棵完全二叉树，有 2^n - 1 个节点。该树的根节点值为 1，对于值为 val 的每个节点（val 在 [1, 2^(n-1) - 1] 范围内），都有两个子节点：

  • 左子节点的值为 2 * val
  • 右子节点的值为 2 * val + 1

还给你一个长度为 m 的二维整数数组 queries，其中 queries[i] = [ai, bi]。对于每个查询，请解决以下问题：

  1. 在值为 ai 和 bi 的节点之间添加一条边
  2. 找到图中环的长度
  3. 删除值为 ai 和 bi 的节点之间添加的边

注意：

  • 环是从同一节点开始和结束的路径，路径中的每条边只访问一次
  • 环的长度是环中访问的边数
  • 添加查询边后，树中两个节点之间可能有多条边

返回一个长度为 m 的数组 answer，其中 answer[i] 是第 i 个查询的答案。

示例 1：

输入：n = 3, queries = [[5,3],[4,7],[2,3]]
输出：[4,5,3]
解释：图中显示了有 2^3 - 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]
解释：图中显示了有 2^2 - 1 个节点的树。红色节点描述了添加边后环中的节点。
- 添加节点 1 和 2 之间的边后，图包含节点 [2,1] 的环。因此第一个查询的答案是 2。删除添加的边。

约束：

  • 2 <= n <= 30
  • m == queries.length
  • 1 <= m <= 10^5
  • queries[i].length == 2
  • 1 <= ai, bi <= 2^n - 1
  • ai != bi

解题思路

这道题的关键在于理解完全二叉树的结构特性和环的形成机制。

核心观察：

  • 在完全二叉树中，当我们在两个节点 a 和 b 之间添加一条边时，形成的环路径为：a → LCA(a,b) → b → a
  • 环的长度 = dist(a, LCA) + dist(b, LCA) + 1（添加的边）

解题思路：

  1. 找最低公共祖先（LCA）：在完全二叉树中，节点编号有特殊性质：

    • 节点 x 的父节点是 x//2
    • 我们可以通过不断向上追溯到根节点来找到两个节点的 LCA

  2. 距离计算：

    • 节点到根的深度 = log2(node) 向下取整
    • 两节点间距离 = depth(a) + depth(b) - 2*depth(LCA)

  3. 优化的 LCA 算法：

    • 同时从两个节点向上移动，直到它们相遇
    • 每次将较大的节点值除以 2（向父节点移动）
    • 移动次数就是到 LCA 的距离

算法步骤：

  1. 对于每个查询 [a, b]
  2. 使用双指针同时从 a 和 b 向根节点移动
  3. 记录移动步数，直到两个指针相遇（找到 LCA）
  4. 环长度 = 总移动步数 + 1

这种方法时间复杂度为 O(log n)，因为树的高度最多为 log(2^n) = n。

代码实现

class Solution {
public:
    vector<int> cycleLengthQueries(int n, vector<vector<int>>& queries) {
        vector<int> result;
        
        for (auto& query : queries) {
            int a = query[0], b = query[1];
            int steps = 1; // 添加的边
            
            // 找到LCA并计算距离
            while (a != b) {
                if (a > b) {
                    a /= 2;
                } else {
                    b /= 2;
                }
                steps++;
            }
            
            result.push_back(steps);
        }
        
        return result;
    }
};

class Solution:
    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        result = []
        
        for a, b in queries:
            steps = 1  # 添加的边
            
            # 找到LCA并计算距离
            while a != b:
                if a > b:
                    a //= 2
                else:
                    b //= 2
                steps += 1
            
            result.append(steps)
        
        return result

public class Solution {
    public int[] CycleLengthQueries(int n, int[][] queries) {
        int[] result = new int[queries.Length];
        
        for (int i = 0; i < queries.Length; i++) {
            int a = queries[i][0], b = queries[i][1];
            int steps = 1; // 添加的边
            
            // 找到LCA并计算距离
            while (a != b) {
                if (a > b) {
                    a /= 2;
                } else {
                    b /= 2;
                }
                steps++;
            }
            
            result[i] = steps;
        }
        
        return result;
    }
}

var cycleLengthQueries = function(n, queries) {
    const result = [];
    
    for (const [a, b] of queries) {
        let nodeA = a, nodeB = b;
        let steps = 1; // 添加的边
        
        // 找到LCA并计算距离
        while (nodeA !== nodeB) {
            if (nodeA > nodeB) {
                nodeA = Math.floor(nodeA / 2);
            } else {
                nodeB = Math.floor(nodeB / 2);
            }
            steps++;
        }
        
        result.push(steps);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(m × n)，其中 m 是查询数量，n 是树的深度，每次查询需要 O(n) 时间找到 LCA
空间复杂度O(1)，只使用常数额外空间（不计算输出数组）

相关题目