First, define a tree node, where the BFSTraversal
is breath-first search, ReconstructBFS
is to construct a tree based on a breadth-first search sequence.
template<typename T>
struct TreeNode
{
T val;
TreeNode *left;
TreeNode *right;
explicit TreeNode(T x) : val(x), left(nullptr), right(nullptr)
{}
static void BFSTraversal(TreeNode *node, void visit(T));
static TreeNode<T> *ReconstructBFS(vector<T> &seq);
};
Then overload the <<
operator, which gives a compiler error that I do not understand. Is there something wrong with my lambda function?
template<typename T>
ostream &operator<<(ostream &os, TreeNode<T> *node)
{
void (*visit)(T) = [&os](T v) -> void
{ os << v << ','; };
// compiler error
// cannot convert 'operator<<(std::ostream&, TreeNode<T>*)
// [with T = int; std::ostream = std::basic_ostream<char>]::<lambda(int)>' to 'void (*)(int)' in initialization
TreeNode<T>::BFSTraversal(node, visit);
return os;
}
I intend to achieve the following code.
auto bfs_seq = vector<int>{1,0,2,3}; // 0 represents `null`
TreeNode* root = ReconstructBFS(bfs_seq);
cout << root;
You can skip this. I am not sure but I think This is not directly relevant to my problem.
The implementation of BFSTraversal
.
template<typename T>
void TreeNode<T>::BFSTraversal(TreeNode *node, void (*visit)(T))
{
if (node)
{
queue<TreeNode *> q{node};
auto level_len = 1, next_level_len = 0;
auto null_val = T();
while (!q.empty())
{
for (auto i = 0; i < level_len; ++i)
{
node = q.front();
q.pop();
if (node == nullptr)
visit(null_val);
else
{
q.push(node->left);
q.push(node->right);
next_level_len += 2;
}
}
level_len = next_level_len;
next_level_len = 0;
}
}
}
The implementation of ReconstructBFS
.
template<typename T>
TreeNode<T> *TreeNode<T>::ReconstructBFS(vector<T> &seq)
{
auto seq_size = seq.size();
if (seq_size == 0) return {};
auto root = new TreeNode<T>(seq[0]);
queue<TreeNode<T> *> q{root};
auto level_len = 1, i = 1;
auto next_level_len = 0;
auto null_val = T();
while (!q.empty())
{
for (auto j = 0; j < level_len; ++j)
{
auto cur_parent = q.front();
q.pop();
auto v = seq[i++];
if (v == null_val) cur_parent->left = v;
else
{
cur_parent->left = new TreeNode(v);
++next_level_len;
}
v = seq[i++];
if (v == null_val) cur_parent->right = v;
else
{
cur_parent->right = new TreeNode(v);
++next_level_len;
}
}
level_len = next_level_len;
next_level_len = 0;
}
return &root;
}
Aucun commentaire:
Enregistrer un commentaire