列表

详情


BM39. 序列化二叉树

描述

请实现两个函数,分别用来序列化和反序列化二叉树,不对序列化之后的字符串进行约束,但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

二叉树的序列化(Serialize)是指:把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串,从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改,序列化的结果是一个字符串,序列化时通过 某种符号表示空节点(#)

二叉树的反序列化(Deserialize)是指:根据某种遍历顺序得到的序列化字符串结果str,重构二叉树。

例如,可以根据层序遍历的方案序列化,如下图:
层序序列化(即用函数Serialize转化)如上的二叉树转为"{1,2,3,#,#,6,7}",再能够调用反序列化(Deserialize)将"{1,2,3,#,#,6,7}"构造成如上的二叉树。

当然你也可以根据满二叉树结点位置的标号规律来序列化,还可以根据先序遍历和中序遍历的结果来序列化。不对序列化之后的字符串进行约束,所以欢迎各种奇思妙想。

数据范围:节点数 ,树上每个节点的值满足
要求:序列化和反序列化都是空间复杂度 ,时间复杂度

示例1

输入:

{1,2,3,#,#,6,7}

输出:

{1,2,3,#,#,6,7}

说明:

如题面图

示例2

输入:

{8,6,10,5,7,9,11}

输出:

{8,6,10,5,7,9,11}

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 2ms, 内存消耗: 536KB, 提交时间: 2021-12-31

/*
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 "#";
        string str = to_string(root->val) + "!";
        char* left = Serialize(root->left);
        char* right = Serialize(root->right);
        char* ret = new char[strlen(left)+strlen(right)+str.size()];
        strcpy(ret, str.c_str());
        strcat(ret, left);
        strcat(ret, right);
        return ret;
    }
    TreeNode* deserialize(char* str, int &p){
        if(str[p] == '#'){
            p++;
            return nullptr;
        }
        bool sign = 1;
        if(str[p] == '-'){
            sign = 0;
            p++;
        }
        int val = 0;
        while(str[p] != '!'){
            val = val * 10 + str[p] - '0';
            p++;
        }
        if(sign == 0) val = -val;
        p++;
        TreeNode* root = new TreeNode(val);
        root->left = deserialize(str, p);
        root->right = deserialize(str, p);
        return root;
    }
    TreeNode* Deserialize(char *str) {
        int p = 0;
        return deserialize(str, p);
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 592KB, 提交时间: 2021-12-05

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    string serializehelp(TreeNode *r){
        queue<TreeNode*> q;
        q.push(r);
        string str = "";
        while(!q.empty()){
            TreeNode* temp = q.front();
            q.pop();
            if(r->val <0){
                if(str==""){
                    str = str+"#";
                }else{
                    str = str+",#";
                }
            }else{
                if(str==""){
                    str = str+to_string(temp->val);
                }else{
                    str = str+","+to_string(temp->val);
                }
            }
            if(temp->val!=-1&&temp->left){
                q.push(temp->left);
            }else if(temp->val!=-1){
                TreeNode *templ = new TreeNode(-1);
                q.push(templ);
            }
            if(temp->right){
                q.push(temp->right);
            }else if(temp->val!=-1){
                TreeNode *templ = new TreeNode(-1);
                q.push(templ);
            }
        }
        return str;
    }
    char* Serialize(TreeNode *root)
    {
        string s;
        queue<TreeNode*> qt;
        qt.push(root);

        while (!qt.empty())
        {
            // pop operator
            TreeNode *node = qt.front();
            qt.pop();
            // process null node
            if (node == nullptr)
            {
                s.push_back('#');
                s.push_back(',');
                continue;
            }
            // process not null node
            s += to_string(node->val);
            s.push_back(',');
            // push operator
            qt.push(node->left);
            qt.push(node->right);

        }

        char *ret = new char[s.length() + 1];
        strcpy(ret, s.c_str());

        return ret;
    }

    
        TreeNode* Deserialize(char *str)
    {
        if (str == nullptr) {
            return nullptr;
        }
        // 可用string成员函数
        string s(str);
        if (str[0] == '#') {
            return nullptr;
        }

        // 构造头结点
        queue<TreeNode*> nodes;
        TreeNode *ret = new TreeNode(atoi(s.c_str()));
        s = s.substr(s.find_first_of(',') + 1);
        nodes.push(ret);
        // 根据序列化字符串再层次遍历一遍,来构造树
        while (!nodes.empty() && !s.empty())
        {
            TreeNode *node = nodes.front();
            nodes.pop();
            if (s[0] == '#')
            {
                node->left = nullptr;
                s = s.substr(2);
            }
            else
            {
                node->left = new TreeNode(atoi(s.c_str()));
                nodes.push(node->left);
                s = s.substr(s.find_first_of(',') + 1);
            }

            if (s[0] == '#')
            {
                node->right = nullptr;
                s = s.substr(2);
            }
            else
            {
                node->right = new TreeNode(atoi(s.c_str()));
                nodes.push(node->right);
                s = s.substr(s.find_first_of(',') + 1);
            }
        }
        return ret;
    }

};

C++ 解法, 执行用时: 2ms, 内存消耗: 612KB, 提交时间: 2022-03-13

/*
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 == nullptr)
            return "#";
        string str = to_string(root -> val);
        str += ',';
        char* left = Serialize(root -> left);
        char* right = Serialize(root -> right);
        char* ch = new char[strlen(left) + strlen(right) + str.size()];
        ch = strcpy(ch, str.c_str());
        strcat(ch, left);
        strcat(ch, right);
        return ch;
    }
    TreeNode* Deserialize(char *str) {
        return deserialize(str);
    }
    TreeNode* deserialize(char* &str){
        if(*str == '#') {
            ++str;
            return nullptr;
        }
        int num = 0;
        while(*str != ',') {
            num = num * 10 + (*str - '0');
            ++str;
        }
        ++str;
        TreeNode* root = new TreeNode(num);
        root -> left = deserialize(str);
        root -> right = deserialize(str);
        return root;
    }
    
};

C++ 解法, 执行用时: 2ms, 内存消耗: 640KB, 提交时间: 2021-12-13

/*
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) {    
        string s;
        queue<TreeNode*> qt;
        qt.push(root);
        
        while(!qt.empty())
        {
            TreeNode *node = qt.front();
            qt.pop();
            if(!node)
            {
                s.push_back('#');
                s.push_back(',');
                continue;
            }
            s += to_string(node->val);
            s.push_back(',');
            
            qt.push(node->left);
            qt.push(node->right);
        }
        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);
        if(str[0]=='#')
            return nullptr;
        queue<TreeNode*> nodes;
        TreeNode *ret = new TreeNode(atoi(s.c_str()));
        s = s.substr(s.find_first_of(',')+1);
        nodes.push(ret);
        while(!nodes.empty() && !s.empty())
        {
            TreeNode *node = nodes.front();
            nodes.pop();
            if(s[0]=='#')
            {
                node->left = nullptr;
                s = s.substr(2);
            }
            else
            {
                node->left = new TreeNode(atoi(s.c_str()));
                nodes.push(node->left);
                s = s.substr(s.find_first_of(',')+1);
            }
            
            if(s[0]=='#')
            {
                node->right = nullptr;
                s = s.substr(2);
            }
            else
            {
                node->right = new TreeNode(atoi(s.c_str()));
                nodes.push(node->right);
                s = s.substr(s.find_first_of(',')+1);
            }
        }
        return ret;
    }
};

Go 解法, 执行用时: 2ms, 内存消耗: 1024KB, 提交时间: 2021-12-06

package main
import . "nc_tools"
import "strings"
import "strconv"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 * 
 * @param root TreeNode类 
 * @return TreeNode类
*/
func Serialize( root *TreeNode ) string {
    // write code here
    var ret []string
    var fn = func(val string){
        ret = append(ret, val)
    }
    serialize(root,fn)
    return strings.Join(ret,",")
}

func serialize(root *TreeNode,fn func(val string)){
    if root == nil{
        fn("#")
        return
    }
    fn(strconv.Itoa(root.Val))
    serialize(root.Left,fn)
    serialize((root.Right),fn)
    
}

func Deserialize( s string ) *TreeNode {
    // write code here
    var str = strings.Split(s,",")
    var fn  func()*TreeNode
    fn = func()*TreeNode{
        if str[0] == "#"{
            str = str[1:]
            return nil
        }
        valInt,_  := strconv.Atoi(str[0])
        str = str[1:]
        return &TreeNode{
            Val:valInt,
            Left:fn(),
            Right:fn(),
        }
    }
    return fn()
}

// func deserialize(s *[]string)*TreeNode{
//     if (*s)[0] == "#"{
//         (*s) = (*s)[1:]
//         return nil
//     }
//     valInt,_  := strconv.Atoi((*s)[0])
//     *s = (*s)[1:]
//     return &TreeNode{
//         Val: valInt,
//         Left: deserialize(s),
//         Right: deserialize(s),
//     }
    
// }








上一题