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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x),left(NULL),right(NULL) {}
 * };
 */
class Codec {
public:

    void change_int_to_string(int val,std::string &str_val)
    {
        std::string tmp;
        while(val)
        {
            tmp += val%10 + ‘0‘;
            val = val/10;
        }
        for(int i=tmp.size()-1; i>=0; --i)
        {
            str_val += tmp[i];
        }
        str_val += ‘#‘;
    }
    
    void BST_pre(TreeNode * node,std::string &data)
    {
        if(!node)
            return;
        std::string str_val;
        change_int_to_string(node->val,str_val);
        data += str_val;
        BST_pre(node->left,data);
        BST_pre(node->right,data);
    }
    
    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 data;
        BST_pre(root,data);
        return data;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.size()==0)
            return NULL;
        vector<TreeNode*> node_vec;
        int val = 0;
        for(int i=0; i<data.size(); ++i)
        {
            if(data[i] == ‘#‘)
            {
                node_vec.push_back(new TreeNode(val));
                val = 0;
            }
            else
            {
                val = val*10 + data[i]-‘0‘;
            }
            
        }
        for(int i=1; i<node_vec.size(); ++i)
        {
            BST_insert(node_vec[0],node_vec[i]);
        }
        return node_vec[0];
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));