leetcode 297. Serialize and Deserialize Binary Tree-蒲公英云

leetcode 297. Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

as "[1,2,3,null,null,4,5]" , just the same as how LeetCode OJ serializes a binary tree . You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

class Codec {
    string my_itoa(int n)
    {
        if (n == 0)
            return "0";
        bool positive = n < 0 ? false : true;
        n = abs(n);
        string re;
        while (n != 0)
        {
            re.insert(re.begin(), n % 10 + '0');
            n /= 10;
        }
        if (!positive)
            re.insert(re.begin(), '-');
        return re;
    }
    int my_atoi(string s)
    {
        bool posivtive = s.front() != '-';
        if (s.front() == '-')
            s.erase(0, 1);
        int re = 0;
        while (!s.empty())
        {
            re = 10 * re + s[0] - '0';
            s.erase(0, 1);
        }
        if (!posivtive)
            re = -re;
        return re;
    }
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == NULL)
            return "#";
        string s;
        vector<TreeNode*>que;
        que.push_back(root);
        while (!que.empty())
        {
            TreeNode*n = que.back();
            que.pop_back();
            if (n == NULL)
                s += "#,";
            else
            {
                s += my_itoa(n->val)+',';
                que.push_back(n->right);
                que.push_back(n->left);
            }
        }
        if (s.back() == ',')
            s.pop_back();
        return s;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data == "#")
            return NULL;
        TreeNode*root = NULL;
        int pos = data.find(',');
        vector<TreeNode*>que;
        while (!data.empty())
        {
            string s;
            if (pos != string::npos)
            {
                s = string(data.begin(), data.begin() + pos);
                data.erase(0, pos + 1);
            }
            else
            {
                s = data;
                data.clear();
            }
            if (s == "#")
            {
                if (que.back()->left != NULL)
                {
                    que.pop_back();
                    pos = data.find(',');
                    continue;
                }
                pos = data.find(',');
                if (pos != string::npos)
                {
                    s = string(data.begin(), data.begin() + pos);
                    data.erase(0, pos + 1);
                }
                else
                {
                    s = data;
                    data.clear();
                }
                if (s == "#")
                    que.pop_back();
                else
                {
                    int val = my_atoi(s);
                    TreeNode*n = new TreeNode(val);
                    que.back()->right = n;
                    que.pop_back();
                    que.push_back(n);
                }
            }
            else
            {
                int val = my_atoi(s);
                if (root == NULL)
                {
                    root = new TreeNode(val);
                    que.push_back(root);
                }
                else
                {
                    TreeNode*n = new TreeNode(val);
                    if (que.back()->left == NULL)
                    {
                        que.back()->left = n;
                        que.push_back(n);
                    }
                    else
                    {
                        que.back()->right = n;
                        que.pop_back();
                        que.push_back(n);
                    }
                }
            }
            pos = data.find(',');
        }
        return root;
    }
};