Serialize and Deserialize Binary Tree

• Medium
• keyword: Recursion, pre-order, BFS, DFS
• 类似: Binary Tree

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.

• 例子:

   1       
  / \   
 /   \  
 -1   2   
    /   
    3

• 如上图: 有2种serialize: pre-order和level-order
• 先说level-order, 因为Leetcode的Binary Tree都是用的level order表示.
  • serialize是: [1,-1,2,#,#,3]
• 再看看pre-order, 则是[1,-1,#,#,2,3,#,#,#]

idea1: level-order

Serialize: BFS, 简单.

• 即通过BFS来做, 注意null的情况. 我一开始想着leaf node不用加null儿子, 但发现这样是不对的, 例如上图中的-1, 他就必须加上null儿子, 否则不知道2是谁的儿子了. 这样会导致结尾多了3的null儿子. 所以我最后还处理了一下stringbuilder.
• 代码如下:

public String serializeTTT(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    if (root == null) return "null";
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
      int sz = q.size();
      for (int i = 0; i < sz; ++i) {
        TreeNode cur = q.poll();
        if (cur == null) {
          sb.append("null,");
          continue;
        } else {
          sb.append(cur.val + ",");
        }
        //if (cur.left == null && cur.right == null && q.size()==1) { 这样做会出错: [1,-1,2,#,#,3]
        //  continue;
        //}
        q.offer(cur.left);
        q.offer(cur.right);
      }
    }
    sb.deleteCharAt(sb.length() - 1);
    String[] sbArr = sb.toString().split(",");
    int i;
    for (i = sbArr.length-1; i >= 0; i--) {
      if (!sbArr[i].equals("null")) {
        break;
      }
    }
    return sb.substring(0, sb.length() - (sbArr.length-1-i)*5);  // remove the trailing null
  }

Deserialize

• 还是用BFS来做. 使用一个global pointer: i指向当前strs(通过split ','得到的string array). 如果str不是null, 则按顺序接到poll出来的cur的左右. 并push会queue, 从而在下一层使用.
• 代码如下, 注意: 这里就不用考虑trailing null.

public TreeNode deserializeTTT(String data) {
    String[] strs = data.split(",");
    Queue<TreeNode> q = new LinkedList<>();
    TreeNode root = strs[0].equals("null") ? null : new TreeNode(Integer.valueOf(strs[0]));
    q.offer(root);
    int i = 1;
    while (!q.isEmpty()) {
      int sz = q.size();
      for (int j = 0; j < sz; ++j) {
        TreeNode node = q.poll();
        if (node == null)  continue;
        if (i < strs.length && !strs[i].equals("null")) {
          node.left = new TreeNode(Integer.valueOf(strs[i++]));
        } else {
          i++;
        }
        if (i < strs.length && !strs[i].equals("null")) {
          node.right = new TreeNode(Integer.valueOf(strs[i++]));
        } else {
          i++;
        }
        q.offer(node.left);
        q.offer(node.right);
      }
    }
    return root;
  }

idea2

• 这也是大部分人的写法, 为什么不用in-order/post-order呢? 因为只有pre-order保存了头节点, 从而可以Deserialize会tree. 而后两者则不行.

Serialize

• 简单的recursion.
• 代码如下

private static final String spliter = ",";
private static final String NN = "null";
public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    buildString(root, sb);
    return sb.toString();
  }

  private void buildString(TreeNode node, StringBuilder sb) {
    if (node == null) {
      sb.append(NN).append(spliter);
    } else {
      sb.append(node.val).append(spliter);
      buildString(node.left, sb);
      buildString(node.right,sb);
    }
  }

Deserialize

• 这个是这题的关键. Serialize都是简单的, 因为按顺序遍历即可.
• 也是pre-order的recursion, 同时使用Queue, 保存的pre-order的序列.
• 代码如下

  // Decodes your encoded data to tree.
  public TreeNode deserialize(String data) {
    Queue<String> nodes = new LinkedList<>();
    nodes.addAll(Arrays.asList(data.split(spliter)));
    return buildTree(nodes);
  }

  private TreeNode buildTree(Queue<String> nodes) {
    String val = nodes.poll();
    if (val.equals(NN))  return null;
    else {
      TreeNode node = new TreeNode(Integer.valueOf(val));
      node.left = buildTree(nodes);
      node.right = buildTree(nodes);
      return node;
    }
  }