leetcode：428. 序列化和反序列化 N 叉树（会员题）
lintcode：1532 · 序列化和反序列N叉树

题目

序列化是将一个数据结构或对象转换成比特流的过程，以便将其存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一或另一计算机环境中重建。
设计一个算法来序列化和反序列化一个 N 叉树。一棵 N 叉树是一棵有根树，其中每个节点的子节点不超过 N 个。序列化/反序列化算法的实现方式没有限制。您只需要确保N叉树可以序列化为字符串，并且该字符串可以反序列化为原始树结构。
例如，你可以序列化如下的 3 叉树 为 [1 [3[5 6] 2 4]]。你不一定要遵循这种格式，发挥创意，自己想出不同的方法。
[困难] 428. 序列化和反序列化 N 叉树 - 图1

示例 1：

  1. 输入：{1,3,2,4#2#3,5,6#4#5#6}
  2. 输出：{1,3,2,4#2#3,5,6#4#5#6}
  3. 解释：如上图
  1. 输入：{1,3,2#2#3}
  2. 输出：{1,3,2#2#3}
  3. 解释：
  4.     1
  5.      / \
  6.     3   2

解答 & 代码

和[困难] 297. 二叉树的序列化与反序列化基本一致，也可以通过先序遍历来序列化，只是 N 叉树的子节点数量不定，因此在序列化的时候，还需要存储每个节点的子节点数量

  1. /**
  2.  * Definition for Directed graph.
  3.  * struct DirectedGraphNode {
  4.  *     int label;
  5.  *     vector<DirectedGraphNode *> neighbors;
  6.  *     DirectedGraphNode(int x) : label(x) {};
  7.  * };
  8.  */
  9.  // 通过括号确定层级和节点的父子关系
  10. class Solution {
  11. private:
  12.     // 递归序列化 N 叉树（先序遍历），结果存储在 result
  13.     void dfsSerialize(DirectedGraphNode* root, string& result)
  14.     {
  15.         if(root == nullptr)                    // 递归结束条件：空节点
  16.         {
  17.             result += "N ";
  18.             return;
  19.         }
  21.         // 先序位置
  22.         result += to_string(root->label);                            // 存储当前节点的值
  23.         result += " " + to_string(root->neighbors.size()) + " ";    // 存储当前节点的子节点数目
  24.         // 递归遍历所有子节点
  25.         for(int i = 0; i < root->neighbors.size(); ++i)
  26.             dfsSerialize(root->neighbors[i], result);
  27.     }
  29.     // 递归反序列化 N 叉树（先序遍历）
  30.     UndirectedGraphNode* dfsDeserialize(istringstream& data)
  31.     {
  32.         string val;
  33.         data >> val;
  34.         if(val == "N")                        // 递归结束条件：空节点
  35.             return nullptr;
  37.         // 先序位置
  38.         UndirectedGraphNode* root = new UndirectedGraphNode(stoi(val));    // 建立当前节点
  39.         data >> val;
  40.         int childCnt = stoi(val);            // 当前节点的子节点数目
  41.         // 递归遍历所有子节点
  42.         for(int i = 0; i < childCnt; ++i)
  43.         {
  44.             UndirectedGraphNode* child = dfsDeserialize(data);
  45.             root->neighbors.push_back(child);
  46.         }
  47.         return root;
  48.     }
  49. public:
  50.     string serialize(vector<DirectedGraphNode*> &nodes) {
  51.         string result;
  52.         if(nodes.size() == 0)
  53.             return "N ";
  55.         dfsSerialize(nodes[0], result);
  56.         // cout << result << endl;
  57.         return result;
  58.     }
  59.     UndirectedGraphNode* deserialize(string &data) {
  60.         // cout << data << endl;
  61.         istringstream istr(data);
  62.         return dfsDeserialize(istr);
  63.     }
  64. };

复杂度分析：设 N 叉树节点数为 m

  • 时间复杂度 O(m)：遍历每个节点
  • 空间复杂度 O(log m)：递归栈深度 = 树深度

执行结果：

  1. 执行结果：通过
  3. 执行用时：41 ms, 在所有 C++ 提交中击败了 76.09% 的用户
  4. 内存消耗：5.47 MB, 在所有 C++ 提交中击败了 76.09% 的用户