Binary Tree Serialization

题目：

Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called 'serialization' and reading back from the file to reconstruct the exact same binary tree is 'deserialization'.

There is no limit of how you deserialize or serialize a binary tree, you only need to make sure you can serialize a binary tree to a string and deserialize this string to the original structure.

接口：

class Solution {
public:
    /**
     * This method will be invoked first, you should design your own algorithm 
     * to serialize a binary tree which denote by a root node to a string which
     * can be easily deserialized by your own "deserialize" method later.
     */
    string serialize(TreeNode *root) {
        // write your code here
    }

    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in 
     * "serialize" method.
     */
    TreeNode *deserialize(string data) {
        // write your code here
    }
};

分析：

首先，我觉得这道题目说30min能做出来无bug是扯淡，给我45分钟我还是写不好...容易出错的地方太多。

其次，如果想deserialize方便，最好用levelorder的bfs。如果用levelorder，先把string解析为一个vector，然后处理。

在处理的过程中，开一个vector，然后定义个int curr来检索，同时设置bool left，用来翻转判断，当bool left == false之后，curr++。相当于，vector里的data过2个，curr进一步。

用一个traversal做出来的还原树，要求记录其中的NULL结点，否则至少需要两个traversal才能还原树。
具体参见Reconstruct的题目。

解法：

class Solution {
public:
    /**
     * This method will be invoked first, you should design your own algorithm 
     * to serialize a binary tree which denote by a root node to a string which
     * can be easily deserialized by your own "deserialize" method later.
     */
    string serialize(TreeNode *root) {
        // write your code here
        if (root == NULL) {
            return "{}";
        }

        string res;
        queue<TreeNode*> Q;
        Q.push(root);
        while (!Q.empty() ) {
            int size = Q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* temp = Q.front();
                Q.pop();
                if (temp != NULL) {
                    Q.push(temp->left);
                    Q.push(temp->right);
                    res  = res + to_string(temp->val) + ",";
                } else {
                    res = res + "#,";
                }
            }
        }
        res.pop_back();
        string lastNode = res.substr(res.size() - 2);
        while (lastNode == ",#") {
            res.pop_back();
            res.pop_back();
            lastNode = res.substr(res.size() - 2);
        }
        res = "{" + res + "}";
        return res;
    }

    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in 
     * "serialize" method.
     */
    vector<string> parseString(string data) {
        int pos = 1;
        vector<string> res;
        while (1) {
            int curr = pos;
            while (data[curr] != ',' && data[curr] != '}') {
                curr++;
            }
            string temp = data.substr(pos, curr - pos);
            res.push_back(temp);
            pos = curr + 1;

            if (data[curr] == '}') {
                break;
            }
        }
        return res;
    } 

    TreeNode *deserialize(string data) {
        // write your code here
        if (data == "{}") {
            return NULL;
        }

        vector<string> splitData = parseString(data);

        vector<TreeNode* > V;
        TreeNode* root = new TreeNode(stoi(splitData[0]) );
        V.push_back(root);

        bool isLeftChild = true;
        int curr = 0;

        for (int i = 1; i < splitData.size(); i++) {
            if (splitData[i] != "#") {
                TreeNode* temp = new TreeNode(stoi(splitData[i]) );
                if (isLeftChild) {
                    V[curr]->left = temp;
                } else {
                    V[curr]->right = temp;
                }
                V.push_back(temp);
            }
            if (!isLeftChild) {
                curr++;
            }
            isLeftChild = !isLeftChild;
        }

        return root;
    }
};