计算存储为向量数组C++的一般树的每个节点的高度

Question

我在C++中以向量数组的形式存储了一个树，使得每行的第一列由该节点的子节点总数组成，然后每行的后续列由该结点的所有子节点的索引组成。

vector <long long int> nodes[N];

例如-有N=8节点，如果v是u的直接子节点，则给定树的节点为

u v
1 2
1 3
2 4
2 5
4 6
4 7
6 8

则矢量CCD_ 4的阵列将是

0. 2 2 3
1. 2 4 5
2. 0
3. 2 6 7
4. 0
5. 1 8
6. 0
7. 0

现在，我想把每个节点的高度保存在一个大小为N的新数组中。我该如何为此开发算法？

Answer 1

您可以使用此函数来计算树中每个节点的高度。

它是一个根为0的树的简单DFS。

int height(vector<int> nodes[], vector<int> &arr, int u, int p){
int ans = 0;
for(int i=1;i<=nodes[u][0];i++){
if(nodes[u][i]!=p){
ans=max(ans, height(nodes, arr, nodes[u][i], u));
}
}
return arr[u] = 1 + ans;
}

该函数可以如下调用：height(nodes, arr, 0, -1)，其中arr是大小为n的空向量，即vector<int> arr(n, 0);

Answer 2

经过一些思考，我可以设计一个迭代解决方案。

int heights[N] = {0};

for(long long int i = N-1;i>=0;i--){

int max = 0;
int no_child = nodes[i][0];

for(int j=1;j<=no_child;j++){
if(heights[nodes[i][j]] > max){
max = heights[nodes[i][j]];
}
}

max++;
heights[i] = max;
}