题解 | #序列化二叉树#

序列化二叉树

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

1. 先序遍历解法

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    const char SEP = '&';
    const char NULL_NODE = '#';
    char* Serialize(TreeNode *root) {    
        if(!root){
            return nullptr;
        }
        stack<TreeNode*> nodes;
        TreeNode* cur = root;
        string s;
        
        while(cur || !nodes.empty()){
            while(cur){
                s.append(to_string(cur->val));
                s.push_back(SEP);
                nodes.push(cur);
                cur = cur->left;
            }
            s.push_back(NULL_NODE);
            s.push_back(SEP);
            cur = nodes.top();
            nodes.pop();
            cur = cur->right;
        }
        s.push_back(NULL_NODE);
        s.push_back(SEP);
        char* ret = new char[s.length() + 1];
        strcpy(ret, s.c_str());
        return ret;
        
    }
    
    TreeNode* Deserialize(char *str) {
        if(!str){
            return nullptr;
        }
        string s(str);
        TreeNode* root = new TreeNode(atoi(s.c_str()));
        s = s.substr(s.find_first_of(SEP) + 1);
        TreeNode* cur = root;
        stack<TreeNode*> nodes;
        while(!s.empty() && (cur || !nodes.empty())){
            while(cur){
                nodes.push(cur);
                if(s[0] == NULL_NODE){
                    cur->left = nullptr;
                }else{
                    cur->left = new TreeNode(atoi(s.c_str()));
                }
                s = s.substr(s.find_first_of(SEP)+1);
                cur = cur->left;
            }
            cur = nodes.top();
            nodes.pop();
            if(s[0] == NULL_NODE){
                cur->right = nullptr;
            }else{
                cur->right = new TreeNode(atoi(s.c_str()));
            }
            s = s.substr(s.find_first_of(SEP)+1);
            cur = cur->right;
        }
        return root;
    }
};

2. 层序遍历解法

class Solution {
public:
    const char SEP = '&';
    const char NULL_NODE = '#';
    char* Serialize(TreeNode *root) {
        if(!root){
            return nullptr;
        }
        queue<TreeNode*> nodes;
        nodes.push(root);
        string serialized_str;
        while(!nodes.empty()){
            TreeNode* head = nodes.front();
            nodes.pop();
            if(head){
                serialized_str.append(to_string(head->val));
                nodes.push(head->left);
                nodes.push(head->right);
            }else{
                serialized_str.push_back(NULL_NODE);
            }
            serialized_str.push_back(SEP);
        }
        char* ret = new char[serialized_str.length() + 1];
        strcpy(ret, serialized_str.c_str());
        return ret;
    }
    TreeNode* Deserialize(char *str) {
        if(!str){
            return nullptr;
        }
        string s(str);
        if(s[0] == NULL_NODE){
            return nullptr;
        }
        queue<TreeNode*> nodes;
        TreeNode* root = new TreeNode(atoi(s.c_str()));
        nodes.push(root);
        s = s.substr(s.find_first_of(SEP)+1);
        
        while(!nodes.empty() && !s.empty()){
            TreeNode* head = nodes.front();
            nodes.pop();
            if(s[0] == NULL_NODE){
                head->left == nullptr;
            }else{
                head->left = new TreeNode(atoi(s.c_str()));
                nodes.push(head->left);
            }
            s = s.substr(s.find_first_of(SEP) + 1);
            
            if(s[0] == NULL_NODE){
                head->right = nullptr;
            }else{
                head->right = new TreeNode(atoi(s.c_str()));
                nodes.push(head->right);
            }
            s = s.substr(s.find_first_of(SEP) + 1);
        }
        return root;
    }
};

3. 中序就不会了。。。。

全部评论

相关推荐

小厂面经,也是我的处女面(30min)1.自我介绍2.spring&nbsp;boot的自动装配原理(好多类和接口的单词都忘了全称是啥了,就说了记得的单词,流程应该说对了吧)3.有用过redis吗?主要是用在实现什么功能(说了技术派用redis的zset来实现排行榜)5.有了解过Redisson吗?讲一下对于分布式锁的了解以及在什么场景下应用(说了秒杀场景)6.对mysql有了解吗?包括它的索引优化和创建(把想起来的全说了)7.了解设计模式吗?比如单例模式,为什么要使用单例模式,它的优点是什么(昨天刚看的设计模式)8.工厂模式有了解吗?主要的使用场景是?(也是昨天刚看的)9.场景题:有7个服务器,需要在早上十点定时的向数据库中的用户表中的用户发短信,如果做到发送的消息不重复,且如果发送失败了需要知道是到哪个用户失败了,这样下次就直接从这个用户开始(我答了用spring&nbsp;task来实现定时,用分布式锁来保证只有一份服务器可以发送消息,用消息队列来存储消息,然后用消息确认机制来保证错误信息的记录,以及在数据库或者业务层面完成消息消费的幂等性)10.场景题:如果在系统启动的时间就将数据库的所有用户相关的信息都读到一个hashmap中(这个没啥思路,没答好)27届的投了一个星期终于有一个面试了,大部分公司都只招26的
inari233:已oc,拒了
查看9道真题和解析
点赞 评论 收藏
分享
评论
1
1
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
牛客网
牛客企业服务