题目描述

blablabla

样例

生成序列样式为8 12 2 # # 6 4 # # # # (最后有一个空格)

C++ 代码

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

    int stringtoint(string data) {
        int val = 0;
        int size = data.size();
        if(data[0] == '-') 
        {
            for(int m = 1; m < size; m ++)  
            {
                val = 10 * val + data[m] - '0';

            } 
            val = -1 * val;
        }
        else 
            for(int m = 0; m < size; m++) 
                val = 10 * val + data[m] - '0';

        return val;
    }
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root) return "";
        queue<TreeNode*> q;
        q.push(root);
        string tmp = "";
        while(!q.empty()) {
            TreeNode* t = q.front();
            q.pop();
            if(!t) tmp += "# ";
            else {
                tmp = tmp + to_string(t->val) + " ";
                q.push(t->left);
                q.push(t->right);
            }

        }

        return tmp;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {


        if(data == "") return NULL;

        queue<TreeNode*> q;
        int i = 0, k = 0;
        while(data[i + k] != ' ') k++;
        int val;
        val = stringtoint(data.substr(i, k));
        TreeNode* root = new TreeNode(val);
        TreeNode* p = root;
        q.push(p);
        while(!q.empty()) {
            TreeNode *t = q.front(); q.pop();

            i = i + k + 1, k = 0;
            while(data[i + k] != ' ') k++;


            if(data.substr(i,k) != "#") {
                val = stringtoint(data.substr(i, k));
                p = new TreeNode(val);
                q.push(p);
                t->left = p;
            }


            i = i + k + 1, k = 0;
            while(data[i + k] != ' ') k++;

            if(data.substr(i,k) != "#") {
                val = stringtoint(data.substr(i, k));
                p = new TreeNode(val);
                q.push(p);
                t->right = p;
            }


        }
        return root;


    }
};