题目分析这道题的关键在于理解完全二叉树的编号规律节点 val 的父节点是 val / 2整数除法。当在两个节点间添加一条边时形成的环长度等于两节点到其最近公共祖先LCA的路径边数之和再加 1新加的边。由于树的高度最多为 30n ≤ 30直接向上跳找 LCA 非常高效每个查询只需 O(log n) 时间。算法思路1. 初始化计数器 cnt 1计入新添加的边2. 当 a ! b 时循环· 如果 a b将 a 移动到其父节点a / 2· 否则将 b 移动到其父节点b / 2· 计数器加 13. 循环结束时cnt 即为环的长度C语言实现c/*** Note: The returned array must be malloced, assume caller calls free().*/int* cycleLengthQueries(int n, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {int* ans (int*)malloc(queriesSize * sizeof(int));*returnSize queriesSize;for (int i 0; i queriesSize; i) {int a queries[i][0];int b queries[i][1];int cnt 1; // 计入新添加的边while (a ! b) {if (a b) {a / 2; // 移动到父节点} else {b / 2;}cnt;}ans[i] cnt;}return ans;}代码说明· 参数说明n 是树的高度实际解题中未直接使用因为编号规律已隐含树结构queries 是查询二维数组queriesSize 是查询数量· 核心循环每次将数值较大的节点上移因为编号越大深度通常越深直到两节点相遇于 LCA· 计数器每上移一次计一条边最后加上新边得到环长复杂度分析· 时间复杂度O(m × log n)其中 m 为查询数n 为树的高度。每个查询最多执行 2×log₂(2ⁿ) 2n 次循环· 空间复杂度O(m) 用于存储结果O(1) 额外空间㇏