劍指Offer-題37（Java版）：序列化與反序列化二叉樹

參考自：《劍指Offer——名企面試官精講典型程式設計題》

題目：序列化與反序列化二叉樹

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

主要思路：

序列化：用前序周遊序列化二叉樹，儲存目前節點值到字元串中，并添加”，”用于分割字元串。若目前節點為空，則使用一個特殊符号（比如”%”）來代替空節點。

反序列化：先分割字元串，儲存節點值到數組中。按前序周遊特點，先擷取根節點，再擷取左子樹，最後擷取右子樹。若節點值為特殊符号，則該節點為空。遞歸該過程，直到周遊完數組。

關鍵點：遞歸，前序周遊

時間複雜度：O(n)

public class SerializeTree
{
    private static StringBuilder serializeString;
    private static int index;

    public static void main(String[] args)
    {
//            10
//         /      \
//        6        14
//       /\        /\
//      4  8     12  16
        TreeNode root = TreeNode.generateBinaryTree();
        String result = serializeTree(root);
        TreeNode deserializeTree = deserializeTree(result);
        print(deserializeTree);
    }

    //前序周遊列印
    private static void print(TreeNode root)
    {
        if (root == null) return;
        System.out.println(root.val);
        print(root.left);
        print(root.right);
    }

    //序列化二叉樹
    private static String serializeTree(TreeNode root)
    {
        serializeString = new StringBuilder();
        serialize(root);
        return serializeString.toString();
    }

    private static void serialize(TreeNode root)
    {
        if (root == null)
        {
            serializeString.append("%,");  //空節點為%
            return;
        }
        //前序周遊
        serializeString.append(root.val).append(",");
        serialize(root.left);
        serialize(root.right);
    }

    //反序列化二叉樹
    private static TreeNode deserializeTree(String str)
    {
        String[] records = str.split(",");
        index = ;
        return deserialize(records);
    }

    private static TreeNode deserialize(String[] records)
    {
        if (index >= records.length) return null;
        //目前節點為空
        if (records[index].equals("%"))
        {
            index++;
            return null;
        }
        int number = Integer.valueOf(records[index++]);
        //先擷取根節點
        TreeNode root = new TreeNode(number);
        //再擷取左子樹，最後擷取右子樹
        root.left = deserialize(records);
        root.right = deserialize(records);
        return root;
    }
}

class TreeNode
{
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x)
    {
        val = x;
    }

//            10
//         /      \
//        6        14
//       /\        /\
//      4  8     12  16
    /**
     * 生成二叉搜尋樹
     * @return
     */
    public static TreeNode generateBinaryTree()
    {
        TreeNode root = new TreeNode();
        TreeNode node6 = new TreeNode();
        TreeNode node14 = new TreeNode();
        TreeNode node4 = new TreeNode();
        TreeNode node8 = new TreeNode();
        TreeNode node12 = new TreeNode();
        TreeNode node16 = new TreeNode();
        connectNode(root, node6, node14);
        connectNode(node6, node4, node8);
        connectNode(node14, node12, node16);
        return root;
    }

    private static void connectNode(TreeNode root, TreeNode left, TreeNode right)
    {
        root.left = left;
        root.right = right;
    }
}