[leetcode/lintcode 题解]大厂算法面试高频题： 序列化和反序列N

描述
序列化是将一个数据结构或对象转换成比特流的过程，以便将其存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一或另一计算机环境中重建。
设计一个算法来序列化和反序列化一个N叉树。一棵N叉树是一棵有根树，其中每个节点的子节点不超过N个。序列化/反序列化算法的实现方式没有限制。您只需要确保N叉树可以序列化为字符串，并且该字符串可以反序列化为原始树结构。
例如，你可以序列化如下的3叉树

为 [1 [3[5 6] 2 4]]。你不一定要遵循这种格式，发挥创意，自己想出不同的方法。
图模型说明: https://www.lintcode.com/help/graph

在线评测地址：领扣题库官网

样例1
输入：{1,3,2,4#2#3,5,6#4#5#6}
输出：{1,3,2,4#2#3,5,6#4#5#6}
解释：如上图

样例2
输入：{1,3,2#2#3}
输出：{1,3,2#2#3}
 3 2

解题思路
题解：基本是dfs分治即可解决，对输入的有向图从1节点开始遍历构造字符串，遍历儿子节点前加入左括号，完成后加入右括号。还原N叉树同样，遇到左括号开始搜索，读取数字存入，遇到右括号退出。

源代码

/**
 * Definition for Directed graph.
 * class DirectedGraphNode {
 * int label;
 * ArrayList DirectedGraphNode neighbors;
 * DirectedGraphNode(int x) { label = x; neighbors = new ArrayList DirectedGraphNode }
 * };
public class Solution {
 public int pos = 1;
 public String dfs(DirectedGraphNode root) {
 String ans="";
 if(root == null)
 return ans;
 ans += "[";
 ans += String.valueOf(root.label);
 for(int i = 0; i root.neighbors.size() ; i++) {
 ans += dfs(root.neighbors.get(i));
 ans += "]";
 return ans;
 public UndirectedGraphNode solve(String data) {
 int num = 0;
 while(data.charAt(pos) = '0' data.charAt(pos) = '9') {
 num *= 10;
 num += data.charAt(pos) - '0';
 pos++;
 UndirectedGraphNode node = new UndirectedGraphNode(num);
 while(pos data.length()) {
 if(data.charAt(pos) == '[' ) {
 ++pos;
 node.neighbors.add(solve(data));
 else if(data.charAt(pos) == ']') {
 pos++;
 return node;
 return null;
 public String serialize(ArrayList DirectedGraphNode nodes) {
 String ans="";
 if(nodes.size() == 0)
 return ans;
 return dfs(nodes.get(0));
 public UndirectedGraphNode deserialize(String data) {
 if(data.length() == 0)
 return null;
 return solve(data);
}

更多题解参考：九章官网solution

本文转自网络，原文链接：https://developer.aliyun.com/article/784393
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！