题解 | #序列化二叉树#

序列化二叉树

http://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84

这道题本身挺简单的,但是坑是真的多,给我整破防了。
先说一下大概的思路,直接用层序遍历来序列化。序列化的时候使用一个队列来辅助将结点值拼接到字符串上,节点为空则拼接#。反序列化时同理,使用队列来辅助反序列化,创建好的节点先入队,并且查看队头结点的情况,若其左结点为空,则将该结点设为队头结点的左结点,若队头结点右结点为空,则将该结点设为队头节点右结点,并将队头出队。
在最开始写好时,两个测试用例无事通过,信心满满,点击提交,用例未通过{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;
    }
};
全部评论

相关推荐

06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
求offer的大角牛:简历写的第一乱,没有突出重点,第二项目太多太杂看不出来有啥核心技术,第三自我评价太多了,第四获得的荣誉没啥含金量,可以不写,反正问题不少
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务