[劍指offer] 序列化二叉樹

本文首發于我的個人部落格： 尾尾部落

題目描述

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

解題思路

1. 對于序列化：使用前序周遊，遞歸的将二叉樹的值轉化為字元，并且在每次二叉樹的結點不為空時，在轉化val所得的字元之後添加一個','作為分割; 對于空節點則以 '#,' 代替。
2. 對于反序列化：将字元串按照“，”進行分割，插入到隊列中，然後依次從隊列中取出字元建立節點，遞歸建立一個二叉樹。

參考代碼

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

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
    String Serialize(TreeNode root) {
        if(root == null){
            return "#,";
        }
        StringBuffer res = new StringBuffer(root.val + ",");
        res.append(Serialize(root.left));
        res.append(Serialize(root.right));
        return res.toString();
    }
    TreeNode Deserialize(String str) {
        String [] res = str.split(",");
        Queue<String> queue = new LinkedList<String>();
        for(int i = 0; i < res.length; i++){
            queue.offer(res[i]);
        }
        return pre(queue);
    }
    TreeNode pre(Queue<String> queue){
        String val = queue.poll();
        if(val.equals("#"))
            return null;
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = pre(queue);
        node.right = pre(queue);
        return node;
    }
}