#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* Mirror(TreeNode* root){
if(root == nullptr)return nullptr;
for(auto child:root->children){
Mirror(child);
}
reverse(root->children.begin(),root->children.end());
return root;
}
TreeNode* removeLeaf(TreeNode* root){
if(root == nullptr)return nullptr;
if (root->children.empty()) {
delete root; // omit if memory is managed elsewhere
return nullptr;
}
for(int i = (int)root->children.size()-1;i>=0;i--){
auto child = root->children[i];
if(child->children.size()==0){
delete child;
root->children.erase(root->children.begin() + i);
}
}
for(auto child:root->children){
removeLeaf(child);
}
return root;
}
void linearise(TreeNode* root){
if(!root)return;
cout<<root->val<<",";
for(auto child : root->children){
cout<<child->val<<",";
linearise(child);
}
}
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);
//TreeNode* newRoot = Mirror(root);
//cout<<"mirror"<<endl;
//displayTree(newRoot);
//TreeNode* leaf = removeLeaf(root);
//displayTree(leaf);
linearise(root);
return 0;
}