1
class Codec {
2
 public:
3
  string pre(TreeNode *root) {
4
    if (root == NULL) return "";
5

6
    int temp = root->val;
7
    string tempz = to_string(temp);
8

9
    string l = pre(root->left);
10
    string r = pre(root->right);
11

12
    return (tempz + "," + l + "," + r);
13
  }
14

15
  vector<int> parse_string(string data) {
16
    vector<int> ans;
17
    string temp = "";
18
    int n = data.size();
19

20
    for (int i = 0; i < n; ++i) {
21
      if (data[i] == ',') {
22
        if (temp.size() == 0)
23
          continue;
24
        else {
25
          int val = stoi(temp);
26
          ans.push_back(val);
27
          temp = "";
28
        }
29
      } else
30
        temp += data[i];
31
    }
32
    return ans;
33
  }
34

35
  TreeNode *make_tree(vector<int> &preorder, int min_val, int max_val, int &preorder_idx, int n) {
36
    if (preorder_idx == n) return NULL;
37
    int val = preorder[preorder_idx];
38
    if (min_val <= val and val <= max_val) {
39
      TreeNode *curr = new TreeNode(val);
40
      preorder_idx++;
41
      curr->left = make_tree(preorder, min_val, val - 1, preorder_idx, n);
42
      curr->right = make_tree(preorder, val + 1, max_val, preorder_idx, n);
43
      return curr;
44
    } else
45
      return NULL;
46
  }
47

48
  string serialize(TreeNode *root) {
49
    string traversal = pre(root);
50
    // cout<<traversal<<endl;
51
    return traversal;
52
  }
53

54
  TreeNode *deserialize(string data) {
55
    if (data.size() == 0) return NULL;
56
    vector<int> traversal = parse_string(data);
57

58
    // for(auto x:traversal)
59
    // cout<<x<<" ";
60

61
    int preorder_idx = 0;
62
    TreeNode *root = make_tree(traversal, INT_MIN, INT_MAX, preorder_idx, traversal.size());
63

64
    return root;
65
  }
66
};