297. 二叉树的序列化与反序列化(层序遍历+字符串处理)

末蓝、 2023-01-12 01:51 98阅读 0赞

\#\#\# 解题思路

层序遍历构造字符串,用特殊符号隔开

在构造树时要新建结点并将第一个结点赋值给root

我是真的烦死了这道题

\#\#\# 代码

class Codec {
    public:
        string serialize(TreeNode* root) {
            string data = "";
            if(root == NULL) return data;
            queue<TreeNode*> q;
            q.push(root);
            while(q.size()){
                int len = q.size();
                while(len--){
                    TreeNode* cur = q.front();
                    q.pop();
                    data += to_string(cur->val)+":";
                    if(cur->left){
                        data+=to_string(cur->left->val);
                        q.push(cur->left);
                    }else data+="N"; //空节点
                    data+="#"; //间隔符
                    if(cur->right){
                        data+=to_string(cur->right->val);
                        q.push(cur->right);
                    }else data+="N";
                    data+="@"; //结束符
                }
            }
            return data;
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            int idx = 0;
            TreeNode* root = NULL;
            queue<TreeNode*> q;
            q.push(root);
            while(idx < data.size()){
                string sroot = "",sleft = "",sright="";
                int nroot,nleft=1e9,nright=1e9;
                while(data[idx] != ':') sroot+=data[idx++];
                if(data[idx] == ':') idx++;
                
                if(data[idx] != 'N'){
                    while(data[idx] != '#') sleft += data[idx++];
                    if(data[idx] == '#') idx++;
                }else idx++;
                if(data[idx] == '#') idx++;
                if(data[idx] != 'N'){
                    while(data[idx] != '@') sright += data[idx++];
                    if(data[idx] == '@') idx++;
                }else idx++;
                if(data[idx] == '@') idx++;
    
                nroot = stoi(sroot);
                if(sleft.size()) nleft = stoi(sleft);
                if(sright.size()) nright = stoi(sright);
    
                TreeNode* cur = q.front();
                q.pop();
                
                if(cur == NULL){
                    cur = new TreeNode(nroot);
                    root = cur;
                }
                
                if(nleft != 1e9) {
                    TreeNode* nl = new TreeNode(nleft);
                    cur->left = nl;
                    q.push(nl);
                }
                if(nright != 1e9){
                    TreeNode* nr = new TreeNode(nright);
                    cur->right = nr;
                    q.push(nr);
                } 
            }
    
            return root;
        }
    };