LeetCode 428. 序列化和反序列化 N 叉树（DFS）

Michael阿明

发布于 2021-02-19 09:49:35

1.1K0

发布于 2021-02-19 09:49:35

文章被收录于专栏：Michael阿明学习之路

文章目录

- 1. 题目
- 2. 解题

1. 题目

序列化是指将一个数据结构转化为位序列的过程，因此可以将其存储在文件中或内存缓冲区中，以便稍后在相同或不同的计算机环境中恢复结构。

设计一个序列化和反序列化 N 叉树的算法。一个 N 叉树是指每个节点都有不超过 N 个孩子节点的有根树。序列化 / 反序列化算法的算法实现没有限制。你只需要保证 N 叉树可以被序列化为一个字符串并且该字符串可以被反序列化成原树结构即可。

例如，你需要序列化下面的 3-叉树。

为 [1 [3[5 6] 2 4]]。你不需要以这种形式完成，你可以自己创造和实现不同的方法。

注意： N 的范围在 [1, 1000] 不要使用类成员 / 全局变量 / 静态变量来存储状态。你的序列化和反序列化算法应是无状态的。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/serialize-and-deserialize-n-ary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：LeetCode 297. 二叉树的序列化与反序列化（前序遍历&层序遍历）

在上题的基础上记录下有多少个子节点

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(Node* root) 
    {
        ostringstream out;
        serialize(root,out);
        return out.str();
    }

    // Decodes your encoded data to tree.
    Node* deserialize(string data) 
    {
        istringstream in(data);
        return deserialize(in);
    }
private:
    void serialize(Node* root,ostringstream &out)
    {
        if(root)
        {
            out<< root->val << ' ';
            out<< root->children.size() << ' ';//记录子节点个数
            for(auto p : root->children)
                serialize(p, out);
        }
        else
            out << "N ";  
    }
    Node* deserialize(istringstream &in)
    {
        string val;
        in >> val;
        if(val == "N"){
            return NULL;
        }
        Node* root = new Node(stoi(val));
        in >> val;
        int n = stoi(val);
        while(n--)//子节点个数
        {
            Node* p = deserialize(in);
            root->children.push_back(p);
        }    
        return root;
    }
};

92 ms 173.1 MB

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/07/14 ，如有侵权请联系 cloudcommunity@tencent.com 删除

文件存储