剑指Offer 37. 序列化二叉树

Description

难度困难：剑指 Offer 37. 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。
示例:
你可以将以下二叉树：
1
/ \
2 3
/ \
4 5
序列化为 “[1,2,3,null,null,4,5]”

Solution

层序遍历解决
序列化的时候，把 null 也当做节点添加到队列中，当取出从队列取出节点时，判断下节点是否为 null，为 null 时，直接打印出 null。注意：LinkedList 实现的 Queue 才允许存入 null 节点。

/*     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null)
            return "[]";
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if (node == null){
                sb.append("null,");
                continue;
            }
            sb.append(node.val + ",");
            queue.offer(node.left);
            queue.offer(node.right);
        }
        sb.deleteCharAt(sb.length()-1);
        sb.append("]");
        return sb.toString();
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("[]"))
            return null;
        String[] vals = data.substring(1, data.length()-1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i = 1;
        while ( !queue.isEmpty()){
            TreeNode node = queue.poll();
            if(!vals[i].equals("null")){
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.offer(node.left);
            }
            i ++;
            if(!vals[i].equals("null")){
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.offer(node.right);
            } 
            i ++;
        }
        return root;
    }
}