[C++] Serialize in Preorder (Small String), Deserialize using Preorder & Implied Inorder
Brief Explanation\n Serialize the BST in preorder.\n Deserialize the preorder from string.\n Sort preorder to get inorder.\n (Inorder of BST is sorted) \uD83D\u
**Brief Explanation**\n* Serialize the BST in preorder.\n* Deserialize the preorder from string.\n* Sort preorder to get inorder.\n *(Inorder of BST is sorted)* \uD83D\uDE00\n* Now generate the BST from Inorder and Preorder traversal.\n\n***problem now reduced to***\nhttps://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/\n\n```\nclass Codec {\npublic:\n\n    // Encodes a tree to a single string.\n    string serialize(TreeNode* root) {\n        stringstream stream;\n        serialize(root, stream);\n        return stream.str();\n    }\n\n    // Decodes your encoded data to tree.\n    TreeNode* deserialize(string data) {\n        stringstream stream(data);\n        deque<int> preorder(istream_iterator<int>{stream}, istream_iterator<int>());\n        deque<int> inorder = preorder;\n        sort(inorder.begin(), inorder.end());\n        return deserialize(preorder, inorder, -1);\n    }\n    \nprivate:\n    void serialize(TreeNode* node, stringstream& stream) {\n        if (!node) {\n            return;\n        }\n        stream << node->val << " ";\n        serialize(node->left, stream);\n        serialize(node->right, stream);\n    }\n    \n    TreeNode* deserialize(deque<int>& preorder, deque<int>& inorder, int stop) {\n        if (preorder.empty()) {\n            return nullptr;\n        }\n        \n        if (inorder.front() == stop) {\n            inorder.pop_front();\n            return nullptr;\n        }\n        \n        TreeNode* node = new TreeNode(preorder.front());\n        preorder.pop_front();\n        node->left = deserialize(preorder, inorder, node->val);\n        node->right = deserialize(preorder, inorder, stop);\n        return node;\n    }\n};\n```
[]