[Leetcode] 1483. Kth Ancestor of a Tree Node (Hard)

概述

題目

https://leetcode.com/problems/kth-ancestor-of-a-tree-node/
給出一個 array 記錄 0 ~ n-1 個點的父點，設計出一 data structure 與 algorithm，可求出第 k 個祖父點

心得

經講解才知道是與有一種解法叫 Binary Lifting，其內容也不算太難，基本上就是用空間換取時間的標準作法，透過多存倍數祖父點來加快搜尋速度

Binary Lifting

思路

from 官神，每個子點都建立一定大小表格，其中分別放置第 1, 2, 4, 8, … 組向上祖父點，而後搜尋速度可加速

程式

class TreeAncestor(object):

    def __init__(self, n, parent):
        """
        :type n: int
        :type parent: List[int]
        """
        # 因題目限次數為 5*10**4，故取 log 為 15.xx，進位成 16 位
        self.cnt = 16

        # 每個子點的 16 個祖點，預處理為 -1
        p = [[-1 for i in range(self.cnt)] for i in range(n)]

        # 第 1 組祖父點，即父點
        for i in range(n):
            p[i][0] = parent[i]

        # 餘下 2, 4, 8, ... 組祖父點，array 以 2^i 次方表示
        for j in range(1, self.cnt):
            for i in range(n):
                if p[i][j-1] != -1:
                    p[i][j] = p[p[i][j-1]][j-1]
        self.p = p

    def getKthAncestor(self, node, k):
        """
        :type node: int
        :type k: int
        :rtype: int
        """
        # 每次花 log n 搜尋
        for j in range(self.cnt):
            if k>>j&1:
                node = self.p[node][j]
                if node == -1:
                    break
        return node


# Your TreeAncestor object will be instantiated and called as such:
# obj = TreeAncestor(n, parent)
# param_1 = obj.getKthAncestor(node,k)