15 基环树的环长

2509. 查询树中环的长度

前言

「力扣题解」系列致力于分享有价值的题目、探讨更优秀的解法。

这是本系列的第 15 篇题解，更多题解关注 Somnia1337@力扣。

题目描述

难度：🔴困难

标签：#树二叉树

给你一个整数 $n$，表示一棵含有 $2^n-1$ 个节点的 完全二叉树。根节点的编号为 $1$，其余每层结点的编号从左至右依次连续填充(见示例图)。

给你一个查询数组，每次查询给出两个结点编号 $(a,b)$，表示在树中新连接一条边 $(a,b)$。注意：原本不存在边 $(a,b)$，且各查询相互独立(边的连接是临时的)。返回一个答案数组，对每次查询，回答连接新边后树上环的长度。

输入: n=3, queries=[[5,3],[4,7],[2,3]]
输出: [4,5,3]
解释:
上面 3 幅图展示了每次查询后树的情况
红色边为查询要求添加的边
红色结点为环上结点
对应的环长分别为 [4,5,3]

解题思路

树 有 $n$ 个结点、$n-1$ 条边，如果再加 1 条边，得到的 $n$ 点 $n$ 边图称为 基环树。本题就是求基环树的环长。

记 $LCA$ 为 $a$ 和 $b$ 的 最近公共祖先(Lowest Common Ancestor)，见下图：

环长即为 $LCA$ 分别到 $a$、$b$ 的距离之和再加上新连接的边 $(a,b)$。

根据题设结点编号的特殊性，每个结点 $e$ 的两个子结点为 $e\ast 2$、$e\ast 2+1$，那么反推得到一个结点 $e$ 的父结点为 $e/2$。

找 $LCA$ 时，在一个 while 内比较 $a$、$b$ 大小(深度，值大者深度大或在同一层)，持续将较深者 /2 上移至其父结点，直到 $a=b$，此时相遇的结点即为 $LCA$。

在 while 的同时进行计数，结束后，本次查询的答案即为计数 +1。

复杂度

• 时间复杂度：$O(mn)$，$m$ 为 queries 的长度，回答每次查询的复杂度为 $O(n)$
• 空间复杂度：$O(1)$

代码

Java

class Solution {
    public int[] cycleLengthQueries(int n, int[][] queries) {
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int cnt = 1, a = queries[i][0], b = queries[i][1];
            while (a != b) {
                if (a > b) a /= 2; // 上移 a
                else b /= 2; // 上移 b
                cnt++; // 计数 +1
            }
            ans[i] = cnt;
        }
        return ans;
    }
}

最后

更多系列「外源推文」&「生活分享」关注公众号：