DeepSeek LeetCode 2509.查询树中环的长度 public int[] cycleLengthQueries(int n, int[][] queries)

这道题的核心是找到两个节点在完全二叉树中的路径长度然后计算环的长度。关键思路1. 完全二叉树的节点编号规律节点 i 的父节点是 i/22. 两个节点之间的路径长度 深度差 2 × LCA深度差3. 环的长度 路径长度 1加回重复的LCA节点算法步骤1. 对每个查询 (a, b)· 记录初始节点 a, b· 分别向上追溯记录路径· 找到它们的最近公共祖先(LCA)· 计算路径长度(depth[a]-depth[lca]) (depth[b]-depth[lca])· 环长 路径长度 1优化方法不需要显式计算深度可以同时向上移动两个节点直到相遇javapublic int[] cycleLengthQueries(int n, int[][] queries) {int[] ans new int[queries.length];for (int i 0; i queries.length; i) {int a queries[i][0];int b queries[i][1];int pathLen 0;// 同时向上移动直到相遇while (a ! b) {if (a b) {a / 2;} else {b / 2;}pathLen;}// 环的长度 路径长度 1ans[i] pathLen 1;}return ans;}时间复杂度 O(q × log n)其中 q 是查询数量n 是树的高度空间复杂度 O(1) 额外空间原理说明· 每次将较大的节点除以2上移一层· 当两个节点相遇时相遇点就是LCA· 移动次数就是两个节点到LCA的边数之和· 加上连接LCA到自身的边形成环这样就能高效计算出每个查询对应的环长。