297. 二叉树的序列化与反序列化

原题链接：297. 二叉树的序列化与反序列化

    solution

/**
 * 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:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(root == NULL) {
            return "_#";
        }
        string res = "_" + to_string(root->val);
        res += serialize(root->left);
        res += serialize(root->right);
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data == "_#") return NULL;
        queue<string> q;

        int n = data.size();
        for(int i = 0;i < n;i++) {
            int j = i;
            string item;
            while(j < n && data[j] != '_') item += data[j++];
            i = j;
            if(item != "") q.push(item);
        }
        return helper(q);
    }

    TreeNode* helper(queue<string>& q)
    {
        string val = q.front();
        q.pop();
        if (val == "#")
            return NULL;
        TreeNode* head = new TreeNode(stoi(val));
        head->left = helper(q);
        head->right = helper(q);
        return head;
    }

};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));