原题链接:
https://leetcode.cn/problems/cycle-length-queries-in-a-tree/

LCA 最长公共祖先问题

LCA问题:
根据完全二叉树的性质 越往下的节点值越大
则从下往上的遍历的过程 即为值见减小的过程
环长 = dist(LCA,a) + dist(LCA,b) + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> cycleLengthQueries(int n, vector<vector<int>>& queries) {
        vector<int>ans;
        for(int i = 0 ; i < queries.size() ; i++){
            int a = queries[i][0], b = queries[i][1];
            int res = 1;
            while(a != b){
                if(a  > b){
                    a = a / 2;
                }else{
                    b = b / 2; 
                }
                res++;
            }

            ans.push_back(res);
        }

        return ans;
    }
};