我需要找到k-ary树的宽度,其中宽度是任何级别的最大节点数。我必须用 C++ 来做。我考虑过 BFS 的修改版本,但没有任何运气。关于如何做到这一点的任何想法?
问问题
426 次
2 回答
1
一种选择是遍历树并跟踪节点深度。每次遇到节点时,您都可以更新与该节点的深度相关的计数器。完成后,您可以找到总值最高的深度,然后将其返回。
在伪代码中:
int treeWidth(Node* root) {
unordered_map<int, int> levelFreqs;
recFindDepths(root, levelFreqs, 0);
int maxCount = -1;
for (auto& keyValue: levelFreqs) {
maxCount = max(maxCount, keyValue.second);
}
return maxCount;
}
void recFindDepths(Node* root, unordered_map<int, int>& levelFreqs,
int depth) {
if (!root) return;
levelFreqs[depth]++;
for (each child) {
recFindDepths(child, levelFreqs, depth + 1);
}
}
希望这可以帮助!
于 2013-06-10T22:38:20.627 回答
0
最大数应为 k^depth,其中根为 depth==0。你的意思是使用的最大值吗?
于 2013-06-10T22:39:50.110 回答