Categorygithub.com/szhou12/leetcode-goleetcode2509-Cycle-Length-Queries-in-a-Tree
package
0.0.0-20241220224003-b7cf03a90b2b
Repository: https://github.com/szhou12/leetcode-go.git
Documentation: pkg.go.dev
Overview
Dependencies
0
Dependents
0

# README

2509. Cycle Length Queries in a Tree

Solution idea

LCA

  • 连接树上任意两个nodes得到的cycle，寻找这个cycle的本质就是找到这两个nodes的 LCA

  • 由于题目给的是完全二叉树，任意一个node X的parent可以容易回溯. 即, parent(X) = X/2

  • 如何在不利用recursion的情况下寻找node a, b 的LCA?

    • a, b 谁的值大，说明那个node较深，优先回溯其parent.
    • 直到 parent(a) == parent(b)

  • 一个node每回溯一次，就相当于找到cycle的一条边，所以 count+1

  • 找到LCA后，count+1 表示连接 node a, b的那条边，这样，就得到了cycle的长度

Time complexity = $O(m*h)$ where $m = $ length of queries, $h = $ height of tree because LCA of any node is at most at root node, which is height farther.

Resource

【每日一题】LeetCode 2509. Cycle Length Queries in a Tree