297. Serialize and Deserialize Binary Tree

Problem:

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

7/30/2018 update:
A easier approach is to use preorder. The below binary tree after encoding should be [1, null, 2, 3, null, null, null]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

public class Codec { private String NULL = "null"; private String COMMA = ","; // Encodes a tree to a single string. public String serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); serialize(root, sb); sb.setLength(sb.length()); return sb.toString(); } private void serialize(TreeNode root, StringBuilder sb) { if (root == null) { sb.append(NULL).append(COMMA); } else { sb.append(root.val).append(COMMA); serialize(root.left, sb); serialize(root.right, sb); } } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if (data == null || data.length() == 0) return null; String[] strs = data.split(COMMA); Queue<String> queue = new LinkedList<>(); for (String str: strs) { queue.offer(str); } return deserialize(queue); } private TreeNode deserialize(Queue<String> queue) { String val = queue.poll(); if (val.equals(NULL)) { return null; } else { TreeNode root = new TreeNode(Integer.valueOf(val)); root.left = deserialize(queue); root.right = deserialize(queue); return root; } } }

--------------------------------------------------------------------------------------------------------------------------------------------

Analysis:

这道题原来是个开放式的问题，只要能serialize 和deserialize 一致，用什么方法都行。一开始我以为leetcode 的方式是，每一层没有的node全部用null占位。其实是分层遍历，把子节点放在后面。

1,null,2,3]

       1
        \
         2
        /
       3

1's children are null and 2. 2's children are 3 and null.

Solution:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
  public String serialize(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode dummy = new TreeNode(0);
        int count = 1;
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur == null) {
                sb.append("null,");
                continue;
            }
            sb.append(cur.val).append(",");
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        sb.setLength(sb.length() - 1);
        sb.append("]");
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data == "") return null;
        data = data.substring(1, data.length() - 1);
        String[] strs = data.split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
        queue.add(root);
        for (int i = 1; i < strs.length; i++) {
            TreeNode cur = queue.poll();
            if (!strs[i].equals("null")) {
                cur.left = new TreeNode(Integer.parseInt(strs[i]));
                queue.offer(cur.left);
            }
            if (!strs[++i].equals("null")) {
                cur.right = new TreeNode(Integer.parseInt(strs[i]));
                queue.offer(cur.right);
            }
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));