題目描述

請實現(xiàn)兩個函數(shù)，分別用來序列化和反序列化二叉樹

二叉樹的序列化是指：把一棵二叉樹按照某種遍歷方式的結(jié)果以某種格式保存為字符串，從而使得內(nèi)存中建立起來的二叉樹可以持久保存。序列化可以基于先序、中序、后序、層序的二叉樹遍歷方式來進行修改，序列化的結(jié)果是一個字符串，序列化時通過 某種符號表示空節(jié)點（#），以 ！ 表示一個結(jié)點值的結(jié)束（value!）。

二叉樹的反序列化是指：根據(jù)某種遍歷順序得到的序列化字符串結(jié)果str，重構(gòu)二叉樹。

題解一

這題的細(xì)節(jié)特別麻煩，折騰了好久才AC成功。本題對于二叉樹的序列化和反序列化的規(guī)則是自定義的，即給定一個二叉樹，可以以自定義的規(guī)則進行序列化，但是要保證反序列化出的二叉樹和輸入的二叉樹一模一樣。我的規(guī)則是在每個節(jié)點后輸出一個逗號，例如：

    1
   / \
  2   3
     / \
    4   5

輸入的二叉樹如上所示，經(jīng)序列化后，得到字符串："1,2,#,#,3,4,#,#,5,#,#,"

這里使用先序遍歷的深度優(yōu)先查找，序列化二叉樹即在先序遍歷二叉樹時將節(jié)點輸出。重點是在碰到空節(jié)點時也要輸出#，因為序列中的#能夠決定二叉樹的結(jié)構(gòu)，沒有這個空節(jié)點#，單靠先序序列是無法恢復(fù)出原來的二叉樹的，即反序列化。

在反序列化時，也是使用先序遍歷的模板，用到了StringBuilder這個數(shù)據(jù)結(jié)構(gòu)，而不直接用String。因為String在java中是不可變對象，是被final修飾的，每次對String修改，都會創(chuàng)建一個新的String，浪費時間和空間。除了StringBuilder，也可以考慮使用字符數(shù)組的方式，這就需要考慮索引的問題了。

下面是參考代碼：

public String serialize(TreeNode root) {
    StringBuilder builder = new StringBuilder();
    serializeHelper(root, builder);
    return builder.toString();
}

private void serializeHelper(TreeNode node, StringBuilder builder) {
    if (node == null) {
        builder.append("#,");
        return;
    }
    builder.append(node.val).append(',');
    serializeHelper(node.left, builder);
    serializeHelper(node.right, builder);
}

public TreeNode deserialize(String str) {
    return deserializeHelper(new StringBuilder(str));
}

private TreeNode deserializeHelper(StringBuilder builder) {
    // 遞歸終止條件與空節(jié)點的處理
    if (builder.length() == 0)
        return null;
    if (builder.charAt(0) == '#') {
        builder.delete(0,2);
        return null;
    }

    // 取出當(dāng)前根節(jié)點的值存進num
    int index = builder.indexOf(",");
    int num = Integer.parseInt(builder.substring(0,index));
    builder.delete(0,index+1);

    // 先序遍歷
    TreeNode root = new TreeNode(num);
    root.left = deserializeHelper(builder);
    root.right = deserializeHelper(builder);
    return root;
}