fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /* A binary tree node has data, pointer to left child
  5.    and a pointer to right child */
  6. struct Node
  7. {
  8.     int data;
  9.     struct Node* left;
  10.     struct Node* right;
  11. };
  12.  
  13. /* Helper function that allocates a new node with the
  14.    given data and NULL left and right pointers. */
  15. struct Node* newNode(int data)
  16. {
  17.   struct Node* node = new Node;
  18.   node->data = data;
  19.   node->left = NULL;
  20.   node->right = NULL;
  21.  
  22.   return(node);
  23. }
  24.  
  25. void serialize(Node *root,vector<int> &);
  26.  
  27.  
  28.  
  29. Node * deSerialize(vector<int> &);
  30.  
  31. /* Computes the number of nodes in a tree. */
  32. int height(struct Node* node)
  33. {
  34.   if (node==NULL)
  35.     return 0;
  36.   else
  37.     return 1 + max(height(node->left), height(node->right));
  38. }
  39.  
  40. void inorder(Node *root)
  41. {
  42.     if (root == NULL)
  43.        return;
  44.     inorder(root->left);
  45.     cout << root->data << " ";
  46.     inorder(root->right);
  47. }
  48. /* A binary tree node has data, pointer to left child
  49.    and a pointer to right child  
  50. struct Node
  51. {
  52.     int data;
  53.     Node* left;
  54.     Node* right;
  55. }; */
  56.  
  57. /*this  function serializes 
  58. the binary tree and stores 
  59. it in the vector A*/
  60. void serialize(Node *root,vector<int> &A)
  61. {
  62.     if(root == NULL)
  63.     {
  64.         A.push_back(-1);
  65.         return;
  66.     }
  67.     A.push_back(root->data);
  68.     serialize(root->left,A);
  69.     serialize(root->right,A);
  70. }
  71.  
  72. /*this function deserializes
  73.  the serialized vector A*/
  74. int ind = 0;
  75. Node * deSerialize(vector<int> &A)
  76. {
  77.    if(ind == A.size()-1 || A[ind] == -1)
  78.    {
  79.        ind += 1;
  80.        cout<<"hai";
  81.        return NULL;
  82.    }
  83.  
  84.    Node *root = newNode(A[ind]);
  85.    ind += 1;
  86.    root->left = deSerialize(A);
  87.    root->right=  deSerialize(A);
  88.    return root;
  89. }
  90.  
  91. /* Driver program to test size function*/
  92. int main()
  93. {
  94.   int t;
  95.   scanf("%d\n", &t);
  96.   while (t--)
  97.   {
  98.      map<int, Node*> m;
  99.      int n;
  100.      scanf("%d",&n);
  101.      int N = n;
  102.      struct Node *root = NULL;
  103.      struct Node *child;
  104.      while (n--)
  105.      {
  106.         Node *parent;
  107.         char lr;
  108.         int n1, n2;
  109.         scanf("%d %d %c", &n1, &n2, &lr);
  110.  
  111.         if (m.find(n1) == m.end())
  112.         {
  113.            parent = newNode(n1);
  114.            m[n1] = parent;
  115.            if (root == NULL)
  116.              root = parent;
  117.         }
  118.         else
  119.            parent = m[n1];
  120.  
  121.         child = newNode(n2);
  122.         if (lr == 'L')
  123.           parent->left = child;
  124.         else
  125.           parent->right = child;
  126.         m[n2]  = child;
  127.      }
  128.     vector<int> A;
  129.     A.clear();
  130.  
  131.     serialize(root,A);
  132.   //  for(int i=0;i<A.size();i++)
  133.     //    cout<<A[i]<<" ";
  134.       //  cout<<endl;
  135.     // inorder(root);
  136.      //cout<<endl;
  137.     Node *tree_made = deSerialize(A);
  138.  
  139.     inorder(tree_made);
  140.     cout<<endl;
  141.  
  142.   }
  143.   return 0;
  144. }
  145.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
2
2
1 2 L 1 3 R
4
10 20 L 10 30 R 20 40 L 20 60 R
stdout
copy 
haihaihaihai2 1 3 
hai
https://ideone.com/uZ89iH
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!