P154 二叉树的序列化和反序列化

描述#

这个题目说的是，你要设计一个算法来序列化和反序列化一棵二叉树。你需要实现两个函数，序列化函数可以把一棵二叉树序列化成一个字符串表示；而反序列化函数可以把这个字符串还原成原来的二叉树。

比如说，给你的二叉树是：
0
/   

1     2
/ 

4   8
你可以把它序列化成字符串：
"[0,1,2,null,null,4,8]"
这是 leetcode 对二叉树的序列化表示，只要你刷过 leetcode，对这个应该不会陌生。
反过来，如果给你这个字符串。你也要能把它还原成原来的二叉树。
注意：序列化和反序列化具体使用什么算法不限，序列化后的字符串也并不是非得使用 leetcode 采用的形式。只要能对一棵二叉树正确地序列化和反序列化即可。

代码#

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(n)
  public String serialize(TreeNode root) {
    if (root == null) return "[]";
    List<TreeNode> trees = new ArrayList<>();
    trees.add(root);
    for (int i = 0; i < trees.size(); ++i) {
      TreeNode node = trees.get(i);
      if (node != null) {
        trees.add(node.left);
        trees.add(node.right);
      }
    }
    while (trees.get(trees.size()-1) == null)
      trees.remove(trees.size()-1);
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < trees.size()-1; ++i) {
      String str = trees.get(i) == null ? "null" : String.valueOf(trees.get(i).val);
      sb.append(str).append(',');
    }
    return "[" + sb.append(trees.get(trees.size()-1).val).toString() + "]";
  }

  // Time: O(n), Space: O(n)
  public TreeNode deserialize(String data) {
    if (data.equals("[]")) return null;
    String[] elems = data.substring(1, data.length()-1).split(",");
    TreeNode[] trees = new TreeNode[elems.length];
    for (int i = 0; i < elems.length; ++i)
      trees[i] = elems[i].equals("null") ? null : new TreeNode(Integer.valueOf(elems[i]));
    int i = 1;
    for (TreeNode tree: trees) {
      if (tree != null) {
        if (i < trees.length) tree.left = trees[i++];
        if (i < trees.length) tree.right = trees[i++];
      }
    }
    return trees[0];
  }

}