劍指offer——序列化二叉樹

1、序列化知識點

一：二叉樹序列化（持久化）

二叉樹的序列化是指：把一棵二叉樹按照某種周遊方式的結果以某種格式儲存為字元串，進而使得記憶體中建立起來的二叉樹可以持久儲存。

序列化可以基于 先序、中序、後序、按層 的二叉樹周遊方式來進行修改。原理都是一樣的（即周遊順序不同而已，對每個結點的處理都是一樣的），序列化的結果是一個字元串，序列化時通過 某種符号表示空節點（#），以 ！ 表示一個結點值的結束（value!）。

這裡以先序周遊的方式進行序列化舉例：

先序序列化二叉樹==定義一個stringbuilder儲存序列過程中的結果：按照先序周遊方式周遊二叉樹，若結點非空則把 “結點值，” append到builder中；若結點空則把 “#，” append到builder中；最後用builder生成字元串就是序列化結果。

二：二叉樹的反序列化

二叉樹的反序列化是指：根據某種周遊順序得到的序列化字元串結果str，重構二叉樹。

先序序列化結果重構二叉樹==String[] nodes=str.split(“，”)；//由每個結點的結束符号劃分序列化結果序列，得到各個結點值；

然後按照先序周遊的順序“根左右”的特性，周遊nodes數組建立二叉樹：目前周遊元素非 # 則作為一個結點插入樹中作為上一結點的左兒子；目前周遊元素為 # 則表示此子樹已結束，周遊下一進制素作為上一結點的右兒子；

即：遇數作左；遇#變向

2、題目描述

請實作兩個函數，分别用來序列化和反序列化二叉樹

3、我的解答

利用前序周遊，遞歸，解答！

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    int index=-;
    String Serialize(TreeNode root) {
        StringBuilder sb=new StringBuilder();
        if(root==null){//遞歸出口，若為空節點，則輸入“#,”并傳回
            sb.append("#,");
            return sb.toString();
        }
        sb.append(root.val+",");//若為非空節點，則輸入“值,”
        sb.append(Serialize(root.left));//遞歸序列化左子樹
        sb.append(Serialize(root.right));//遞歸序列化右子樹 
        return sb.toString();
  }
    TreeNode Deserialize(String str) {
        index++;
        int len=str.length();
        if(index>=len){
            return null;
        }
        String[] str1=str.split(",");//分割字元串
        TreeNode node=null;
        if(!str1[index].equals("#")){//重構二叉樹
            node=new TreeNode(Integer.valueOf(str1[index]));
            node.left=Deserialize(str);
            node.right=Deserialize(str);
        }
        return node;
    }
}
           

參考知識點：

Java知識點積累——equals與”==”的比較分析