[LeetCode 449] 序列化和反序列化二叉搜索树

449. 序列化和反序列化二叉搜索树

将二叉搜索树前序化，再按前序可以还原出原来的二叉搜索树。
对于一般的树来说，这个过程不是可逆的，一般的树需要前序和中序一起才能还原出来。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Codec {
    public:
        string int2str(int a) {
            string str="";
            if(a==0)return string("0");
            while(a) {
                char c=a%10+'0';
                str=c+str;
                a/=10;
            }
            return str;
        }

        int str2int(string str,int &i) {
            int res=0;
            while(str[i]!='#') {
                res*=10;
                res+=str[i]-'0';
                i++;
            }
            i++;
            return res;
        }

        void preorder(TreeNode *node,string &str) {
            if(!node)return;
            str+=int2str(node->val);
            str+='#';
            if(node->left)preorder(node->left,str);
            if(node->right)preorder(node->right,str);
        }

        void BST_insert(TreeNode *node,TreeNode *insert_node) {
            if(insert_node->val<node->val) {
                if(node->left)
                    BST_insert(node->left,insert_node);
                else
                    node->left=insert_node;
            } else {
                if(node->right)
                    BST_insert(node->right,insert_node);
                else
                    node->right=insert_node;
            }
        }

        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            string str;
            preorder(root,str);
            return str;
        }

        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            if(data=="")return NULL;
            int i=0;
            int t=str2int(data,i);
            TreeNode *root=new TreeNode(t);
            
            while(i<data.size()) {
                t=str2int(data,i);
                TreeNode* insert_node=new TreeNode(t);
                BST_insert(root,insert_node);
            }
            return root;
        }
};


int main() {
    TreeNode *a1=new TreeNode(8);
    TreeNode *b1=new TreeNode(3);
    TreeNode *b2=new TreeNode(10);
    TreeNode *c1=new TreeNode(1);
    TreeNode *c2=new TreeNode(6);
    TreeNode *c3=new TreeNode(15);

    a1->left=b1;
    a1->right=b2;
    b1->left=c1;
    b1->right=c2;
    b2->right=c3;

    Codec c;
    string str=c.serialize(a1);
    TreeNode *res=c.deserialize(str);
    string tmp;
    c.preorder(res,tmp);
    cout<<tmp;


    return 0;
}