題目描述：

給你一棵樹，樹上有 n 個節(jié)點，按從 0 到 n-1 編號。樹以父節(jié)點數組的形式給出，其中 parent[i] 是節(jié)點 i 的父節(jié)點。樹的根節(jié)點是編號為 0 的節(jié)點。

樹節(jié)點的第 k 個祖先節(jié)點是從該節(jié)點到根節(jié)點路徑上的第 k 個節(jié)點。

實現(xiàn) TreeAncestor 類：

TreeAncestor（int n， int[] parent） 對樹和父數組中的節(jié)點數初始化對象。
getKthAncestor(int node, int k) 返回節(jié)點 node 的第 k 個祖先節(jié)點。如果不存在這樣的祖先節(jié)點，返回 -1 。

示例 1：

輸入：
[“TreeAncestor”,“getKthAncestor”,“getKthAncestor”,“getKthAncestor”]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

輸出：
[null,1,0,-1]

解釋：
TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);

treeAncestor.getKthAncestor(3, 1); // 返回 1 ，它是 3 的父節(jié)點
treeAncestor.getKthAncestor(5, 2); // 返回 0 ，它是 5 的祖父節(jié)點
treeAncestor.getKthAncestor(6, 3); // 返回 -1 因為不存在滿足要求的祖先節(jié)點

提示：

1 <= k <= n <= 5 * 10⁴
parent[0] == -1 表示編號為 0 的節(jié)點是根節(jié)點。
對于所有的 0 < i < n ，0 <= parent[i] < n 總成立
0 <= node < n
至多查詢 5 * 10⁴ 次

解題思路一：暴力解法會超時！【一級一級往上跳，效率太低】

class TreeAncestor:

    def __init__(self, n: int, parent: List[int]):
        self.n = n
        self.parent = parent


    def getKthAncestor(self, node: int, k: int) -> int:
        res = 0
        while k:
            res = self.parent[node]
            node = res
            if node == -1:
                return -1
            k -= 1
        return res



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

時間復雜度：O(n)
空間復雜度：O(n²)

解題思路二：倍增，利用二進制運算，例如13 = 1101。我們動態(tài)規(guī)劃記住第2的階乘的父親節(jié)點即可。每次查找都直接查一次表。

這里注意是：2^j-1 + 2^j-1 = 2^j

class TreeAncestor:

    def __init__(self, n: int, parent: List[int]):
        self.log = 16
        self.ancestors = [[-1] * self.log for _ in range(n)]
        for i in range(n):
            self.ancestors[i][0] = parent[i]
        for j in range(1, self.log):
            for i in range(n):
                if self.ancestors[i][j - 1] != -1:
                    self.ancestors[i][j] = self.ancestors[self.ancestors[i][j - 1]][j - 1]   

    def getKthAncestor(self, node: int, k: int) -> int:
        for j in range(self.log):
            if (k>>j) & 1: 
                node = self.ancestors[node][j]
                if node == -1:
                    return -1
        return node

時間復雜度：O(nlogn)
空間復雜度：O(nlogn)

解題思路三：0

時間復雜度：O(n)
空間復雜度：O(n)文章來源地址http://www.zghlxwxcb.cn/news/detail-853108.html

到了這里，關于LeetCode-1483. 樹節(jié)點的第 K 個祖先【樹 深度優(yōu)先搜索 廣度優(yōu)先搜索 設計 二分查找 動態(tài)規(guī)劃】的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！