题解 | #序列化二叉树#

序列化二叉树

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. 中序就不会了。。。。

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 12:11
点赞 评论 收藏
分享
后来123321:别着急,我学院本大二,投了1100份,两个面试,其中一个还是我去线下招聘会投的简历,有时候这东西也得看运气
无实习如何秋招上岸
点赞 评论 收藏
分享
积极的小学生不要香菜:你才沟通多少,没500不要说难
点赞 评论 收藏
分享
来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

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