Serialize and deserialize binary tree

Question

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.

Example

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"

Solution

• DFS, use the preorder approach but needs to be careful for ‘,’. For the deserialization part, we pass the queue for polling element each time until meet the ‘#’, which returns null.
• BFS, use the level traversal.

Code

// time:O(n) space:O(n)
// Encodes a tree to a single string.
  public String serialize(TreeNode root) {
      if (root == null) return "";
      Queue<TreeNode> queue = new LinkedList<>();
      StringBuilder sb = new StringBuilder();
      queue.offer(root);
      sb.append(root.val);
      while (!queue.isEmpty()) {
          int size = queue.size();
          for (int i = 0; i < size; i++) {
              TreeNode cur = queue.poll();
              if (cur.left == null) {
                  sb.append(",null");
              } else if (cur.left != null) {
                  sb.append("," + cur.left.val);
                  queue.offer(cur.left);
              }
              if (cur.right == null) {
                  sb.append(",null");
              } else if (cur.right != null) {
                  sb.append("," + cur.right.val);
                  queue.offer(cur.right);
              }
          }
      }
      return sb.toString();
  }

  // Decodes your encoded data to tree.
  public static TreeNode deserialize(String data) {
      if (data == null || data.length() == 0) return null;
      String[] strs = data.split(",");
      TreeNode head = new TreeNode(Integer.parseInt(strs[0]));
      Queue<TreeNode> queue = new LinkedList<>();
      int index = 1;
      queue.offer(head);
      while (!queue.isEmpty() && index < strs.length) {
          TreeNode node = queue.poll();
          if (!strs[index].equals("null")) {
              node.left = new TreeNode(Integer.parseInt(strs[index]));
              queue.offer(node.left);
          }
          index++;
          if (!strs[index].equals("null")) {
              node.right = new TreeNode(Integer.parseInt(strs[index]));
              queue.offer(node.right);
          }
          index++;
      }
      return head;
  }


// time:O(n) space:O(n)
  // Encodes a tree to a single string.
  public String serialize2(TreeNode root) {
      if (root == null) return "#,";
      String left = serialize(root.left);
      String right = serialize(root.right);
      return root.val + "," + left + right;
  }

  // Decodes your encoded data to tree.
  public TreeNode deserialize2(String data) {
      if (data == null || data.length() == 0) return null;
      String[] strs = data.split(",");
      Queue<String> queue = new LinkedList<>();
      queue.addAll(Arrays.asList(strs));
      return helper(queue);
  }

  public TreeNode helper(Queue<String> queue) {
      String str = queue.poll();
      if (str.equals("#")) return null;
      TreeNode newNode = new TreeNode(Integer.parseInt(str));
      newNode.left = helper(queue);
      newNode.right = helper(queue);
      return newNode;
  }