原题链接
题目解析
要求编写一个TreeAncestor类,需要为其写两个函数。该类是一个无规律的多叉树,多叉树的父节点一定是0号节点
1. TreeAncestor(int n, vector<int>& 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^4
parent[0] == -1
表示编号为0
的节点是根节点。- 对于所有的
0 < i < n
,0 <= parent[i] < n
总成立 0 <= node < n
- 至多调用
5 * 10^4
次getKthAncestor
解题:
两种不合题意的解法:
直接暴力求解:
超时
class TreeAncestor {
public:
TreeAncestor(int n, vector<int>& parent) {
tmp = {parent.begin(),parent.end()};
}
int getKthAncestor(int node, int k) {
while(k--)
{
if(node == 0)
return -1;
node = tmp[node];
}
return node;
}
vector<int> tmp;
};
构造函数时间复杂度o(n)空间复杂度o(n)
get函数时间复杂度o(k) 空间复杂度o(1)
假设调用a次get:总时间复杂度o(k*a+n)空间复杂度o(n)
优化暴力
超空间
在暴力解法中每次调用get都会从node开始一直向前算,这些计算很可能在之前的遍历中都算过了。如果我们在执行循环之前把所有的情况都算出来,之后调用get时就可以直接得到。
class TreeAncestor {
public:
TreeAncestor(int n, vector<int>& 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;
else
return r[node][k];
}
vector<int> tmp;
vector<vector<int>> 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;
vector<vector<int>>a;
TreeAncestor(int n, vector<int>& parent)
{
a.resize(n, vector<int>(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,a2=0;
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))
感谢观看!!!!