297. Serialize and Deserialize Binary Tree

Reference: LeetCode
Difficulty: Hard

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.

Example:

You may serialize the following tree:
    1
   / \
  2   3
     / \
    4   5
as "[1,2,3,null,null,4,5]"

Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Analysis

BFS

Note:

• Check the null case.
• Handle , in the string. Remove it in the end.
• Use StringBuffer.
• Compatible with null nodes.

Time: $O(N)$ if using StringBuffer for string concatenation.
Space: $O(N)$ since we need to keep the entire tree.

Serialize:

    1
   / \
  2   3
     / \
    4   5
Result: "1,2,3,null,null,4,5,null,null,null,null"

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
  if (root == null) {
    return null;
  }
  StringBuffer sb = new StringBuffer();
  serializeHelper(root, sb);
  sb.setLength(sb.length() - 1); // "remove the last ','"
  
  return sb.toString();
}

private void serializeHelper(TreeNode root, StringBuffer sb) {
  if (root == null) {
    return;
  }
  Queue<TreeNode> queue = new LinkedList<>();
  queue.offer(root);
  
  while (queue.size() > 0) {
    int childSize = queue.size();
    for (int i = 0; i < childSize; ++i) {
      TreeNode p = queue.poll();
      if (p == null) {
        sb.append("null,");
      } else {
        sb.append(p.val + ",");
        queue.offer(p.left);
        queue.offer(p.right);
      }
    }
  }
}

Deserialize:

• Handle the base cases.
• Before the while loop, handle the root node first. So you don’t need an extra dummy node.

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
  if (data == null || data.length() == 0) {
    return null;
  }
  List<Integer> list = parseString(data);
  Queue<TreeNode> queue = new LinkedList<>();
  int index = 0;
  TreeNode root = new TreeNode(list.get(index));
  queue.offer(root);
  index = 1;
  while (queue.size() > 0) {
    int childSize = queue.size();
    for (int i = 0; i < childSize; ++i) {
      TreeNode curr = queue.poll();
      if (curr == null) continue;
      // left
      Integer val = list.get(index);
      curr.left = (val != null) ? new TreeNode(val) : null; // can omit index checking
      index += 1;
      // right
      val = list.get(index);
      curr.right = (val != null) ? new TreeNode(val) : null;
      index += 1;
      queue.offer(curr.left); // may be null
      queue.offer(curr.right);
    }
  }
  return root;
}

private List<Integer> parseString(String data) {
  String[] parsedStrings = data.split(",");
  List<Integer> result = new ArrayList<>();
  for (String s : parsedStrings) {
    result.add((s.equals("null")) ? null : Integer.parseInt(s));
  }
  return result;
}

DFS (Solution)

• We don’t need to remove the last ,. The return list after split does not include "".
• If root is null, the string is null.

Time: $O(N)$ if using StringBuffer for string concatenation.
Space: $O(N)$ since we need to keep the entire tree.

Serialize:

public String serialize(TreeNode root) {
  StringBuffer sb = new StringBuffer();
  rserialize(root, sb);
  return sb.toString();
}

private void rserialize(TreeNode root, StringBuffer sb) {
  if (root == null) {
    sb.append("null,");
    return;               // very important
  }
  sb.append(root.val + ",");
  rserialize(root.left, sb);
  rserialize(root.right, sb);
}

Deserialize:

• In rdeserialize, null check for L is not necessary. We assume the input is a valid preorder input.

public TreeNode deserialize(String data) {
  String[] dataArray = data.split(",");
  List<String> dataList = new LinkedList<>(Arrays.asList(dataArray));
  return rdeserialize(dataList);
}

private TreeNode rdeserialize(List<String> L) {
  if (L.get(0).equals("null")) {
    L.remove(0);
    return null;
  }
  TreeNode root = new TreeNode(Integer.valueOf(L.get(0)));
  L.remove(0);
  root.left = rdeserialize(L);
  root.right = rdeserialize(L);

  return root;
}