做网站做本地服务器,wordpress查询收录,免费psd模板素材,广州seo快速排名原题链接 1483. 树节点的第 K 个祖先 - 力扣#xff08;LeetCode#xff09; 题目解析 要求编写一个TreeAncestor类#xff0c;需要为其写两个函数。该类是一个无规律的多叉树#xff0c;多叉树的父节点一定是0号节点 1. TreeAncestor(int n, vectorintLeetCode 题目解析 要求编写一个TreeAncestor类需要为其写两个函数。该类是一个无规律的多叉树多叉树的父节点一定是0号节点 1. TreeAncestor(int n, vectorint parent) n为parent的长度也为多叉树的节点个数parent中存的是每个节点的父节点的编号例如parent[3] 1代表3号节点的父节点是1号节点 2. int getKthAncestor(int node, int k) node为节点序号k是一个计数器该函数要求返回node节点的第k辈祖先节点的序号如果不存在返回-1
1 k n 5 * 10^4parent[0] -1 表示编号为 0 的节点是根节点。对于所有的 0 i n 0 parent[i] n 总成立0 node n至多调用 5 * 10^4 次getKthAncestor
解题
两种不合题意的解法
直接暴力求解:
超时
class TreeAncestor {
public:TreeAncestor(int n, vectorint parent) {tmp {parent.begin(),parent.end()};}int getKthAncestor(int node, int k) {while(k--){if(node 0)return -1;node tmp[node];}return node;}vectorint tmp;
};
构造函数时间复杂度o(n)空间复杂度o(n)
get函数时间复杂度o(k) 空间复杂度o(1)
假设调用a次get:总时间复杂度o(k*an)空间复杂度o(n)
优化暴力
超空间
在暴力解法中每次调用get都会从node开始一直向前算这些计算很可能在之前的遍历中都算过了。如果我们在执行循环之前把所有的情况都算出来之后调用get时就可以直接得到。
class TreeAncestor {
public:TreeAncestor(int n, vectorint parent) {tmp { parent.begin(),parent.end() };r.resize(tmp.size());for (int i 1; i tmp.size(); i){for (int j i; j 0; j tmp[j]){r[i].push_back(j);}}}int getKthAncestor(int node, int k) {if (k r[node].size())return -1;elsereturn r[node][k];}vectorint tmp;vectorvectorint r;
};
构造函数时间复杂度o(n*n)空间复杂度o(n*n)
get函数时间复杂度o(1) 空间复杂度o(1)
假设调用a次get:总时间复杂度o(n*n)空间复杂度o(n*n)
倍增记录法
既然优化暴力法会超空间限制想办法只取一部分的数据进行记录即可。
class TreeAncestor
{
public:const int num 16;vectorvectorinta;TreeAncestor(int n, vectorint parent) {a.resize(n, vectorint(num, -1));for (int i 0; i n; i){a[i][1] parent[i];}for (int j 2; j num; j){for (int i 0; i n; i){if (a[i][j-1] ! -1)a[i][j] a[a[i][j - 1]][j - 1];}}}int getKthAncestor(int node, int k) {int tmp 0;while (k ! 0){if (node -1)return -1;int a1 1,a20;while (a1 k)a1 * 2,a2;k - a1 / 2;node a[node][ a2 ];}return node;}
};
构造函数时间复杂度o(n*log(n))空间复杂度o(n*log(n))
get函数时间复杂度o(log(k)) 空间复杂度o(1)
假设调用a次get:总时间复杂度o(n*log(n)a*log(k))空间复杂度o(n*log(n)) 感谢观看
