使用预定义函数签名的级别顺序遍历的尾部递归

Question

我的问题是如何使用尾部递归以级别顺序遍历二进制树，并以特定格式打印它。

Binary Tree
__ 60 _ 
|        |
__ 50 _     100 _ 
|       |         |
30      55        1000 
output  "60 : 50, 100 : 30, 55, 1000"

我的代码片段和它的工作：

void LevelOrderTraversalTailRecur(BinaryTreeNode* root, int level, vector<vector<int>>& vec) {
if (root == nullptr) return;

if (vec.size() < level) {
auto v{std::vector<int>{}};
vec.push_back(v);
}
vec[level - 1].push_back(root->data);
if (root->left != nullptr) {
LevelOrderTraversalTailRecur(root->left, level+1, vec);
}
if (root->right != nullptr) {
LevelOrderTraversalTailRecur(root->right, level+1, vec);
} 
}
void LevelOrderTraversal(BinaryTreeNode* root) {
if (root == nullptr) {
cout << "null";
return; 
}
std::vector<std::vector<int>> vec;
LevelOrderTraversalTailRecur(root, 1, vec); 
// ....
// convert the vector into a string
}

但是我想直接使用接口CCD_ 1而不是向量<矢量>。我怎样才能做到这一点？

谢谢！

Answer 1

实现级别顺序遍历的一种常见方法是将属于一个级别的所有树节点存储在一个向量中，然后迭代递减一个级别。

void LevelOrderTraversal(BinaryTreeNode* root) {
int level = 1;
std::vector<BinaryTreeNode*> pending = { root };
while (!pending.empty()) {
// Produce the requested output
auto it = pending.cbegin();
if (level > 1) std::cout << ": ";
std::cout << it->data;
for (; it != pending.cend(); it++) {
std::cout << ", " << it->data;
}
std::vector<BinaryTreeNode*> next;
for (auto node : pending) {
if (node->left)  next.push_back(node->left);
if (node->right) next.push_back(node->right);
}
std::swap(pending, next);
level++;
}