vivek_ragi

SERIALIZE_AND_DESERIALIZE_AND_BINARY_TREE

Jun 21st, 2021
525
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Codec {
  11. public:
  12.     string encoded = "";
  13.     string inordered = "";
  14.    
  15.     void preorder(TreeNode* node) {
  16.         if(node == NULL) {
  17.             encoded += "NULL,";
  18.             return ;
  19.         }
  20.         encoded += to_string(node->val) + ",";
  21.        
  22.         preorder(node -> left);
  23.         preorder(node -> right);
  24.        
  25.     }
  26.     // 1,2,NULL,NULL,3,4,NULL,NULL,5,NULL,NULL,
  27.    
  28.     // Encodes a tree to a single string.
  29.     string serialize(TreeNode* root) {
  30.         preorder(root);
  31.         // cout << encoded << " ";
  32.         return encoded;
  33.     }
  34.    
  35.     queue<string> preprocess(string data) {
  36.         string str = "";
  37.         queue<string> q;
  38.        
  39.         for(int i = 0; i < data.size(); ++i) {
  40.            
  41.             if(data[i] == ',') {
  42.                 q.push(str);
  43.                 str = "";
  44.             }
  45.             else {
  46.                 str+= data[i];
  47.             }
  48.         }
  49.        
  50.         return q;
  51.     }
  52.    
  53.     TreeNode* construct(queue<string> &q) {
  54.         string str = q.front();
  55.         q.pop();
  56.        
  57.         if(str == "NULL") {
  58.             return NULL;
  59.         }
  60.        
  61.         TreeNode* node = new TreeNode(stoi(str));
  62.         node -> left = construct(q);
  63.         node -> right = construct(q);
  64.        
  65.         return node;
  66.     }
  67.  
  68.     // Decodes your encoded data to tree.
  69.     TreeNode* deserialize(string data) {
  70.        
  71.         queue<string> q = preprocess(data);
  72.        
  73.        
  74.        
  75.         return construct(q);
  76.     }
  77. };
  78.  
  79. // Your Codec object will be instantiated and called as such:
  80. // Codec ser, deser;
  81. // TreeNode* ans = deser.deserialize(ser.serialize(root));
RAW Paste Data