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. TreeNode* findTail(TreeNode* root){
  57. while(root->children.size()>0){
  58. root = root->children[0];
  59. }
  60. return root;
  61. }
  62. TreeNode* linearise(TreeNode* root){
  63. if(!root)return nullptr;
  64. for(auto child : root->children){
  65. //cout<<child->val<<",";
  66. linearise(child);
  67. }
  68. while(root->children.size()>1){
  69. int n = root->children.size()-1;
  70. TreeNode* lastChild = root->children[n];
  71. TreeNode* secondLast = root->children[n-1];
  72. TreeNode* tail = findTail(secondLast);
  73. root->children.erase(root->children.begin()+n);
  74. tail->children.push_back(lastChild);
  75. }
  76. return root;
  77. }
  78. TreeNode* buildTree(vector<int>&arr){
  79. if(arr.empty()||arr[0]==-1){
  80. return nullptr;
  81. }
  82.  
  83. TreeNode* root = new TreeNode(arr[0]);
  84.  
  85. stack<TreeNode*>st;
  86. st.push(root);
  87.  
  88. for(int i = 1 ; i<arr.size();i++){
  89. TreeNode* node = st.top();;
  90.  
  91. if(arr[i]==-1){
  92. st.pop();
  93. }else{
  94. TreeNode* newNode = new TreeNode(arr[i]);
  95. node->children.push_back(newNode);
  96. st.push(newNode);
  97. }
  98. }
  99. return root;
  100. }
  101. void displayTree(TreeNode* root){
  102. if(root == nullptr)return;
  103. if(root)cout<<root->val<<"->";
  104. // if(root->children)cout<<root->children->val<<",";
  105.  
  106. for(auto child: root->children){
  107. cout<<child->val<<",";
  108. }
  109. cout<<endl;
  110. for(auto child: root->children){
  111. displayTree(child);
  112. }
  113. }
  114. int main() {
  115. vector<int>arr = {1,2,4,-1,5,-1,-1,3,6,-1,7,-1,-1,-1};
  116. TreeNode* root = buildTree(arr);
  117. //displayTree(root);
  118. //level(root);
  119. //TreeNode* newRoot = Mirror(root);
  120. //cout<<"mirror"<<endl;
  121. //displayTree(newRoot);
  122. //TreeNode* leaf = removeLeaf(root);
  123. //displayTree(leaf);
  124. TreeNode* nr = linearise(root);
  125. displayTree(nr);
  126. return 0;
  127. }
Success #stdin #stdout 0s 544KB
stdin
Standard input is empty
stdout
1->2,
2->4,
4->5,
5->3,
3->6,
6->7,
7->