树节点挑战的第k个祖先

Question

挑战如下：

您将看到一棵树，其中有n个节点，编号从0到n-1，形式为 父数组，其中父[i]是节点i的父。树根 是节点0

实现函数getKthAncestor（intnode，intk）以返回第k个 给定节点的祖先。如果没有这样的祖先，返回-1

树节点的第k个祖先是该节点路径中的第k个节点 节点到根

例如：

输入：

["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);  // returns 1 which is the parent of 3
treeAncestor.getKthAncestor(5, 2);  // returns 0 which is the grandparent of 5
treeAncestor.getKthAncestor(6, 3);  // returns -1 because there is no such ancestor

限制条件：

1 <= k <= n <= 5*10^4
parent[0] == -1 indicating that 0 is the root node.
0 <= parent[i] < n for all 0 < i < n
0 <= node < n
There will be at most 5*10^4 queries.

我很难理解一个人的解决方案。有人愿意解释一下他的最佳解决方案是如何工作的吗？在最近的leetcode竞赛中，这是一个新的挑战，没有重复

class TreeAncestor(object):

    def __init__(self, n, parent):
        self.pars = [parent]
        self.n = n
        for k in range(17):
            row = []
            for i in range(n):
                p = self.pars[-1][i]
                if p != -1:
                    p = self.pars[-1][p]
                row.append(p)
            self.pars.append(row)


    def getKthAncestor(self, node, k):
        """
        :type node: int
        :type k: int
        :rtype: int
        """
        i = 0
        while k:
            if node == -1: break
            if (k&1):
                node = self.pars[i][node]
            i += 1
            k >>= 1
        return node

Answer 1

哇。这是一个很酷的解决方案

解决方案基于两个想法：

• 在构建期间构建祖先矩阵（self.pars）
• 将祖先图分解为大小为1、2、4、8等（2^n）的步骤

self.pars是一个矩阵，其中行号n表示行中第i个元素的2^n个祖先（n从0开始）。例如，在第3行中，我们将拥有树中节点中所有元素的第8个祖先

然后在查询时，该算法将请求分解为一系列日志（k）步骤，以获取节点的第k个祖先。每一步都是k的二进制表示中的一个数字

例如，考虑k＝6。9的二进制表示为1-1-0：

• 数字0（最后一个）是0，所以什么也不要做
• 数字1是1。2^1是2，所以获取我们正在查看的节点的第二个祖先
• 数字2也是1。2^2是4，因此获取当前节点的第四个祖先

我们完成了-分3步，我们一路到达目标节点