#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
int val;
vector<TreeNode*>children;
TreeNode(int val):val(val),children({}){};
};
void level(TreeNode* root){
if(root == nullptr)return;
queue<TreeNode*>q;
q.push(root);
while(!q.empty()){
auto n = q.size();
for(int i = 0 ; i< n;i++){
auto u = q.front();q.pop();
cout<<u->val<<",";
for(auto child: u->children){
q.push(child);
}
}
cout<<endl;
}
}
TreeNode* buildTree(vector<int>&arr){
if(arr.empty()||arr[0]==-1){
return nullptr;
}
TreeNode* root = new TreeNode(arr[0]);
stack<TreeNode*>st;
st.push(root);
for(int i = 1 ; i<arr.size();i++){
TreeNode* node = st.top();;
if(arr[i]==-1){
st.pop();
}else{
TreeNode* newNode = new TreeNode(arr[i]);
node->children.push_back(newNode);
st.push(newNode);
}
}
return root;
}
void displayTree(TreeNode* root){
if(root == nullptr)return;
if(root)cout<<root->val<<"->";
// if(root->children)cout<<root->children->val<<",";
for(auto child: root->children){
cout<<child->val<<",";
}
cout<<endl;
for(auto child: root->children){
displayTree(child);
}
}
int main() {
vector<int>arr = {1,2,4,-1,5,-1,-1,3,6,-1,7,-1,-1,-1};
TreeNode* root = buildTree(arr);
displayTree(root);
level(root);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnN0cnVjdCBUcmVlTm9kZXsKCWludCB2YWw7Cgl2ZWN0b3I8VHJlZU5vZGUqPmNoaWxkcmVuOwoJVHJlZU5vZGUoaW50IHZhbCk6dmFsKHZhbCksY2hpbGRyZW4oe30pe307Cn07Cgp2b2lkIGxldmVsKFRyZWVOb2RlKiByb290KXsKCWlmKHJvb3QgPT0gbnVsbHB0cilyZXR1cm47CglxdWV1ZTxUcmVlTm9kZSo+cTsKCXEucHVzaChyb290KTsKCQoJd2hpbGUoIXEuZW1wdHkoKSl7CgkJYXV0byBuID0gcS5zaXplKCk7CgkJZm9yKGludCBpID0gMCA7IGk8IG47aSsrKXsKCQkJYXV0byB1ID0gcS5mcm9udCgpO3EucG9wKCk7CgkJCQoJCQljb3V0PDx1LT52YWw8PCIsIjsKCQkJCgkJCWZvcihhdXRvIGNoaWxkOiB1LT5jaGlsZHJlbil7CgkJCQlxLnB1c2goY2hpbGQpOwoJCQl9CgkJfQoJCWNvdXQ8PGVuZGw7Cgl9CgkKfQoKVHJlZU5vZGUqIGJ1aWxkVHJlZSh2ZWN0b3I8aW50PiZhcnIpewoJaWYoYXJyLmVtcHR5KCl8fGFyclswXT09LTEpewoJCXJldHVybiBudWxscHRyOwoJfQoJCglUcmVlTm9kZSogcm9vdCA9IG5ldyBUcmVlTm9kZShhcnJbMF0pOwoJCglzdGFjazxUcmVlTm9kZSo+c3Q7CglzdC5wdXNoKHJvb3QpOwoJCmZvcihpbnQgaSA9IDEgOyBpPGFyci5zaXplKCk7aSsrKXsKCVRyZWVOb2RlKiBub2RlID0gc3QudG9wKCk7OwoJCglpZihhcnJbaV09PS0xKXsKCQlzdC5wb3AoKTsKCX1lbHNlewoJCVRyZWVOb2RlKiBuZXdOb2RlID0gbmV3IFRyZWVOb2RlKGFycltpXSk7CgkJbm9kZS0+Y2hpbGRyZW4ucHVzaF9iYWNrKG5ld05vZGUpOwoJCXN0LnB1c2gobmV3Tm9kZSk7Cgl9Cn0KcmV0dXJuIHJvb3Q7Cn0Kdm9pZCBkaXNwbGF5VHJlZShUcmVlTm9kZSogcm9vdCl7CglpZihyb290ID09IG51bGxwdHIpcmV0dXJuOwoJaWYocm9vdCljb3V0PDxyb290LT52YWw8PCItPiI7Ci8vCWlmKHJvb3QtPmNoaWxkcmVuKWNvdXQ8PHJvb3QtPmNoaWxkcmVuLT52YWw8PCIsIjsKCQogICAgZm9yKGF1dG8gY2hpbGQ6IHJvb3QtPmNoaWxkcmVuKXsKICAgIGNvdXQ8PGNoaWxkLT52YWw8PCIsIjsKICAgIH0KICAgIGNvdXQ8PGVuZGw7CiAgICBmb3IoYXV0byBjaGlsZDogcm9vdC0+Y2hpbGRyZW4pewogICAgIGRpc3BsYXlUcmVlKGNoaWxkKTsKICAgIH0KICAgIAp9CmludCBtYWluKCkgewoJdmVjdG9yPGludD5hcnIgPSB7MSwyLDQsLTEsNSwtMSwtMSwzLDYsLTEsNywtMSwtMSwtMX07CiAgICBUcmVlTm9kZSogcm9vdCA9IGJ1aWxkVHJlZShhcnIpOyAgCiAgICBkaXNwbGF5VHJlZShyb290KTsKICAgIGxldmVsKHJvb3QpOwoJcmV0dXJuIDA7Cn0=
1->2,3,
2->4,5,
4->
5->
3->6,7,
6->
7->
1,
2,3,
4,5,6,7,