题解 | #序列化二叉树#

这道题本身挺简单的，但是坑是真的多，给我整破防了。
先说一下大概的思路，直接用层序遍历来序列化。序列化的时候使用一个队列来辅助将结点值拼接到字符串上，节点为空则拼接#。反序列化时同理，使用队列来辅助反序列化，创建好的节点先入队，并且查看队头结点的情况，若其左结点为空，则将该结点设为队头结点的左结点，若队头结点右结点为空，则将该结点设为队头节点右结点，并将队头出队。
在最开始写好时，两个测试用例无事通过，信心满满，点击提交，用例未通过{100,50,##,50}，噩梦开始。
因为最初审题不细致，没看到结点取值为0<=val<=100，我默认值是在0-9之间的个位数了。虽然这对整个程序的逻辑框架完全没有影响，但是意味着要添加很大的工作量去处理十位数以及百位数。
因为字符串处理这块确实基础不太牢，同时这块地坑也是真的多，添加多位数处理的时间占了整道题的2/3以上，期间我真是被整的多次破防。最后专门写了个函数来处理。
空间复杂度方面，最多用到一维数组，无递归，空间复杂为O(n)。时间复杂度方面，涉及到循环遍历，基本逻辑仅用到一重循环，在字符串处理时用到了一个嵌套的二重循环，不过并不是完全嵌套，仅是轻度嵌套，时间复杂度比O(n)稍大。

ps: 题目里面给你带点字符串处理的这种题做多了真的折寿。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    char* Serialize(TreeNode *root) {
        if(!root){
            return nullptr;
        }
        queue<TreeNode*> qe;
        qe.push(root);
        TreeNode* p = root;
        string s;
        while(qe.size() > 0){
            if(!qe.front()){
                s += "#,";
                qe.pop();
                continue;
            }
            TreeNode* temp = qe.front();
            qe.pop();
            s += to_string(temp->val);
            s += ',';
            qe.push(temp->left);
            qe.push(temp->right);
        }
        char* c = new char[100];
        strcpy(c,s.data());
        return c;
    }
    TreeNode* Deserialize(char *str) {
        if(!str){
            return nullptr;
        }
        vector<string> s = getNum(str);
        TreeNode* head = new TreeNode(atoi(s[0].c_str()));
        TreeNode* p;
        queue<TreeNode*> qe;
        qe.push(head);
        int i = 1;
        while(i < s.size()){
            bool flag = false;
            if(s[i] == "#"){
                flag = true;
            }
            if(!flag){
                p = new TreeNode(atoi(s[i].c_str()));
                qe.push(p);
            }
            i++;
            if(qe.front()->left && !flag){
                qe.front()->right = p;
                qe.pop();
            }
            else if(!flag){
                qe.front()->left = p;
            }
            else{
                if(qe.front()->left){
                    qe.pop();
                }
                else{
                    if(s[i] == "#"){
                        qe.pop();
                        i++;
                    }
                    else{
                        TreeNode* np = new TreeNode(atoi(s[i].c_str()));
                        qe.push(np);
                        qe.front()->right = np;
                        qe.pop();
                        i++;
                    }
                }
            }
        }
        return head;
    }
    vector<string> getNum(char* c){
        vector<string> s;
        string temp = "";
        string origin(c);
        int i = 0;
        while(c[i]){
            if(c[i] == '#'){
                s.push_back("#");
                i += 2;
            }
            else{
                int j = i+1;
                while(c[j]){
                    if(c[j] == ','){
                        break;
                    }
                    j++;
                }
                string sub = origin.substr(i,j-i);
                s.push_back(sub);
                i = j + 1;
            }
        }
        return s;
    }
};