fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct TreeNode{
  4. int val;
  5. vector<TreeNode*>children;
  6. TreeNode(int val):val(val),children({}){};
  7. };
  8.  
  9. void level(TreeNode* root){
  10. if(root == nullptr)return;
  11. queue<TreeNode*>q;
  12. q.push(root);
  13.  
  14. while(!q.empty()){
  15. auto n = q.size();
  16. for(int i = 0 ; i< n;i++){
  17. auto u = q.front();q.pop();
  18.  
  19. cout<<u->val<<",";
  20.  
  21. for(auto child: u->children){
  22. q.push(child);
  23. }
  24. }
  25. cout<<endl;
  26. }
  27.  
  28. }
  29. TreeNode* Mirror(TreeNode* root){
  30. if(root == nullptr)return nullptr;
  31. for(auto child:root->children){
  32. Mirror(child);
  33. }
  34. reverse(root->children.begin(),root->children.end());
  35. return root;
  36. }
  37. TreeNode* removeLeaf(TreeNode* root){
  38. if(root == nullptr)return nullptr;
  39.  
  40. if (root->children.empty()) {
  41. delete root; // omit if memory is managed elsewhere
  42. return nullptr;
  43. }
  44. for(int i = (int)root->children.size()-1;i>=0;i--){
  45. auto child = root->children[i];
  46. if(child->children.size()==0){
  47. delete child;
  48. root->children.erase(root->children.begin() + i);
  49. }
  50. }
  51. for(auto child:root->children){
  52. removeLeaf(child);
  53. }
  54. return root;
  55. }
  56.  
  57. void linearise(TreeNode* root){
  58. if(!root)return;
  59. cout<<root->val<<",";
  60. for(auto child : root->children){
  61. //cout<<child->val<<",";
  62. linearise(child);
  63. }
  64. }
  65. TreeNode* buildTree(vector<int>&arr){
  66. if(arr.empty()||arr[0]==-1){
  67. return nullptr;
  68. }
  69.  
  70. TreeNode* root = new TreeNode(arr[0]);
  71.  
  72. stack<TreeNode*>st;
  73. st.push(root);
  74.  
  75. for(int i = 1 ; i<arr.size();i++){
  76. TreeNode* node = st.top();;
  77.  
  78. if(arr[i]==-1){
  79. st.pop();
  80. }else{
  81. TreeNode* newNode = new TreeNode(arr[i]);
  82. node->children.push_back(newNode);
  83. st.push(newNode);
  84. }
  85. }
  86. return root;
  87. }
  88. void displayTree(TreeNode* root){
  89. if(root == nullptr)return;
  90. if(root)cout<<root->val<<"->";
  91. // if(root->children)cout<<root->children->val<<",";
  92.  
  93. for(auto child: root->children){
  94. cout<<child->val<<",";
  95. }
  96. cout<<endl;
  97. for(auto child: root->children){
  98. displayTree(child);
  99. }
  100. }
  101. int main() {
  102. vector<int>arr = {1,2,4,-1,5,-1,-1,3,6,-1,7,-1,-1,-1};
  103. TreeNode* root = buildTree(arr);
  104. //displayTree(root);
  105. //level(root);
  106. //TreeNode* newRoot = Mirror(root);
  107. //cout<<"mirror"<<endl;
  108. //displayTree(newRoot);
  109. //TreeNode* leaf = removeLeaf(root);
  110. //displayTree(leaf);
  111. linearise(root);
  112. return 0;
  113. }
Success #stdin #stdout 0s 544KB
stdin
Standard input is empty
stdout
1,2,4,5,3,6,7,