[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}
解释：如上图

        

          
        
        
        

          

          AI 代码解读
        
      
      

样例2
输入：{1,3,2#2#3}
输出：{1,3,2#2#3}
解释：
          1
         / \
        3   2

        

          
        
        
        

          

          AI 代码解读
        
      
      

解题思路
题解：基本是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);
    }
}

        

          
        
        
        

          

          AI 代码解读
        
      
      

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