【Leetcode】428. Serialize and Deserialize N-ary Tree

题目地址：

https://leetcode.com/problems/serialize-and-deserialize-n-ary-tree/description/

给定一棵多叉树，要求实现其序列化和反序列化函数。多叉树节点的定义如下：

class Node {
public:
  int val;
  vector<Node *> children;
  Node() {}
  Node(int _val) {
    val = _val;
  }
  Node(int _val, vector<Node *> _children) {
    val = _val;
    children = _children;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

给个多叉树的例子：

序列化的方式有很多种，我们这里采用一种“括号层次”的方法，思路是DFS。在序列化的时候，我们规定，对于每个节点，如果这个节点有孩子，那么其孩子都在这个节点紧跟的括号里，并且这些孩子的“括号深度”都相等。这样在反序列化的时候，括号深度每进一步，也就说明了走到了下一层。如上图的多叉树，其序列化之后就是1(2(5,6)3(7)4)，由于$1$后面跟着一个括号，所以我们就知道了括号里深度相等的数字都是其儿子，即$2,3,4$都是其儿子；类似的，由于$2$后面跟着一个括号，从而我们知道$5,6$是其儿子。同一深度的儿子需要区分开来，所以我们中间加个逗号。那么序列化函数是很好写的：

string serialize(Node *root) {
  string s;
  dfs(root, s);
  return s;
}

void dfs(Node *cur, string &s) {
  if (!cur) return;
  s += to_string(cur->val) + ",";
  if (cur->children.empty()) return;

  if (s.back() == ',') s.pop_back();
  s += '(';
  for (auto *ne: cur->children) dfs(ne, s);
  if (s.back() == ',') s.pop_back();
  s += ')';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

上面要注意几个细节，为了节省空间，我们在节点有孩子或者该节点是其父亲的最后一个孩子的情况下，将其后面的逗号去掉了。同时，如果一个节点有孩子，那么其后面会接一对封闭括号，那么这个节点与其右边的兄弟节点也不需要逗号的分隔就可以区分。当然，当这个节点是叶子的时候，后面需要强制加逗号，否则无法区分其和其兄弟节点。这造成了一个副作用，如果整棵树只有一个树根，序列化之后会以逗号结尾。但以逗号结尾也意味着整棵树只有一个树根，我们可以在序列化的时候特判。空树也是一种特殊情况，其也不以括号结尾。别的情况，序列化的结果都是以右括号结尾的。

序列化的过程比较复杂。首先特判掉两个特殊情况，即空串（对应空树），和以逗号结尾（对应整棵树只有一个树根节点）。对于一般情况，算法如下：
1、开一个栈，同时开始遍历字符串；
2、如果遇到数字，那么将整个数字截取出来，new出节点，这个节点要么是树根（从而没有父亲），也就是当栈空的时候，那么就将该节点入栈；如果栈不空，那么我们保持栈顶为DFS树的上一层节点，即当前节点为其儿子，从而加入其儿子列表中；
3、如果遇到左括号，此时说明要进入下一层了，这里有个关键操作，如果当前栈顶的儿子列表不空，我们需要将其最后一个儿子入栈。这是因为我们要保持栈顶是当前遍历的节点的父亲。如果栈顶儿子列表为空，那么下一层的节点都是栈顶的子孙，我们不需要做什么；但是如果栈顶儿子列表不空，进入下一层的时候，其实下一层节点的父亲就是栈顶的最后一个儿子。以上面的图为例，其序列化为1(2(5,6)3(7)4)。当遍历到3(的这个左括号的时候，当前栈顶还是$1$（因为我们要保持栈顶为当前遍历的节点的父亲），那么进入下一层的时候，父亲应该变成$3$了，而$3$恰好是$3$自己的父亲的最后一个孩子。
4、如果遇到右括号，说明当前栈顶的所有孩子都遍历完了，我们要回到上一层，栈pop。这里需要注意，当栈顶就是树根的时候，pop掉树根之后就找不到了（事实上最后一个pop的元素也必然是树根），所以我们干脆将栈pop的元素直接记为树根变量，那么全pop完之后，那个树根变量就是真正的树根。

代码如下：

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

  void dfs(Node *cur, string &s) {
    if (!cur) return;
    s += to_string(cur->val) + ",";
    if (cur->children.empty()) return;

    if (s.back() == ',') s.pop_back();
    s += '(';
    for (auto *ne: cur->children) dfs(ne, s);
    if (s.back() == ',') s.pop_back();
    s += ')';
  }

  // Decodes your encoded data to tree.
  Node *deserialize(string s) {
    // 两个特例
    if (s.empty()) return nullptr;
    if (s.back() == ',') return new Node(stoi(s.substr(0, s.size() - 1)));
    Node *root = nullptr;
    stack<Node *> stk;
    for (int i = 0; i < s.size(); i++) {
      if (s[i] == '(') {
        auto children = stk.top()->children;
        if (children.size()) stk.push(children.back());
      } else if (isdigit(s[i])) {
        int j = i;
        while (j < s.size() && isdigit(s[j])) j++;
        Node *node = new Node(stoi(s.substr(i, j - i)));
        if (stk.size()) stk.top()->children.push_back(node);
        else stk.push(node);
        i = j - 1;
	  } else if (s[i] == ')') {
        root = stk.top();
        stk.pop();
      }
    }

    return root;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

序列化和反序列化的时间复杂度都是$O(n)$，空间都是$O(h)$。

还有一种比较简单的BFS的序列化方法。我们直接对树BFS，每个节点对应的序列化的部分要含其值和其孩子个数。例如上面的树的序列化即为1,3,2,2,3,1,4,0,5,0,6,0,7,0,，开头的1,3表示BFS的时候当前节点值为$1$，有$3$个孩子，这样由BFS性质，我们就知道了其三个孩子就是后面的2,2,3,1,4,0，即值为$2,3,4$的三个节点。这样就能反序列化的时候用BFS再将树构造出来。代码如下：

class Codec {
 public:
  // Encodes a tree to a single string.
  string serialize(Node* root) {
    string s;
    if (!root) return s;
    queue<Node*> q;
    q.push(root);
    while (q.size()) {
      auto* t = q.front();
      q.pop();
      s += to_string(t->val) + "," + to_string(t->children.size()) + ",";
      for (auto* ne : t->children) q.push(ne);
    }
    return s;
  }

  // Decodes your encoded data to tree.
  Node* deserialize(string s) {
    if (s.empty()) return nullptr;
    int idx = 0;
    auto [val, cnt] = get_num(s, idx);
    Node* root = new Node(val);
    queue<pair<Node*, int>> q;
    q.push({root, cnt});
    while (idx < s.size()) {
      auto t = q.front();
      q.pop();
      Node* node = t.first;
      int cnt = t.second;
      for (int i = 0; i < cnt; i++) {
        auto [val, child_cnt] = get_num(s, idx);
        auto* child = new Node(val);
        node->children.push_back(child);
        q.push({child, child_cnt});
      }
    }

    return root;
  }

  // 从i开始截取两个数，第一个数为节点的值，第二个为其孩子数量
  pair<int, int> get_num(string& s, int& i) {
    int j = i;
    while (j < s.size() && isdigit(s[j])) j++;
    int val = stoi(s.substr(i, j - i));
    i = j + 1;
    j = i;
    while (j < s.size() && isdigit(s[j])) j++;
    int cnt = stoi(s.substr(i, j - i));
    i = j + 1;
    return {val, cnt};
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

时空复杂度$O(n)$。