1483. 树节点的第 K 个祖先

本文主要是介绍1483. 树节点的第 K 个祖先，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1483. 树节点的第 K 个祖先

---

题目链接：1483. 树节点的第 K 个祖先

代码如下：

//倍增
//参考leetcode官方题解
class TreeAncestor {
public:TreeAncestor(int n, vector<int>& parent) {ancestors=vector<vector<int>>(n,vector<int>(Log,-1));for(int i=0;i<n;i++){ancestors[i][0]=parent[i];}for(int j=1;j<Log;j++){for(int i=0;i<n;i++){if(ancestors[i][j-1]!=-1){ancestors[i][j]=ancestors[ancestors[i][j-1]][j-1];}}}}int getKthAncestor(int node, int k) {for(int i=0;i<Log;i++){if((k>>i)&1){node=ancestors[node][i];if(node==-1)    return -1;}}return node;}private:constexpr static int Log=16;vector<vector<int>> ancestors;};/*** Your TreeAncestor object will be instantiated and called as such:* TreeAncestor* obj = new TreeAncestor(n, parent);* int param_1 = obj->getKthAncestor(node,k);*/

这篇关于1483. 树节点的第 K 个祖先的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---