[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}
解釋：
          1
         / \
        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