Leetcode題解 Python：Kth Ancestor of a Tree Node

有 n 個 node，編號為[0, n-1]，給一個 parent ，parent[i] 代表第 i 個 node 的 parent 為第 parent[i] 節。

然後給一 node 編號與 k ，要找出其第 k 個祖先。若沒有則回傳 -1 。

難的不是在於能不能順利找到，找到是難度 easy 的問題。難在於能不能「快速」地找到。

我在過程中有試過保存 2 跳的祖先，最糟也能在 25000 跳內解決，不過會超時。

關聯是一對一的，如果為每個node做map，即root到node的每node，就可以 1 跳解決，但是記憶體會爆，O(N**2) Space，因為每node的map都是不一樣的。

這題的關鍵在於要再哪一塊做取捨，如果純照parent跳，會用 O(N) Time。而且本題「大量」執行查詢，最多50000次，那會使沒做查詢優化的超時。

雖然我做了 2 跳祖先，但不夠，仍是 O(N) Time。如果換成保存「指數」跳的祖，就能把查詢變成 O(logN) Time，才有辦法應付大量的查詢。

依 parnet 可以找到 1(2**0) 跳的祖先，那 2(2**1) 跳的是1跳的再1跳，那 4(2**2) 跳呢？是2跳的再2跳。依此類推。

如果有 5 個 node ，那保存到 4(2**2)跳 的袓先就夠了；如果有 8 個 node，那保存到 8(2**3)跳。

因此要保存多少，看總數取log2決定，長度為 log2(n) + 1，而 + 1 是給 1(2**0)跳 空間。 

長度為16的話，代表最多也只會用到16次跳去找到第k個祖先。只有65535會用到16跳，因為其二進位有16個1。

這樣的保存轉換使 __init__() 會用上 O(NlogN) Time，而查詢會變成 O(logN) Time，但大量的查詢使其整體近 O(logN) Time，在效能與記憶體做最好的平衡。

Python

class TreeAncestor:
    def __init__(self, n: int, parent):
        m = int(math.log2(n)) + 1
        self.table = [[-1 for _ in range(m)] for _ in range(n)]      
        for p in range(1,n):       
            self.table[p][0] = parent[p]
            for k in range(1, m):
                self.table[p][k] = self.table[self.table[p][k-1]][k-1]
                if self.table[p][k] == -1: break

    def getKthAncestor(self, node: int, k: int) -> int:
        while k and node != -1:
            pos = int(math.log2(k))
            node = self.table[node][pos]
            k -= 1 << pos
        return node