Serialize and Deserialize Binary Tree

Leave a comment

October 30, 2016 by oneOokay

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.


树:[1,2,3,4,null,5,6]. serialization的format: null节点用#表示,每个节点之间用’,’分隔.

  • pre-order 遍历:结果是:”1,2,4,#,#,#,3,5,#,#,6,#,#”
    • divide & conquer: Recursive DFS, 最优最简单.
    • Iterative:用stack + while loop
  • BFS层遍历serialization: 结果是:”1,2,3,4,#,5,6,#,#,#,#,#,#”
    • 叶子节点的左右节点为##,空节点不会再有子节点. 所以这个并不是一个满二叉树.
    • Iterative:用queue + while loop和i

pre-order:

  1. serialization :
    • divide & conquer: buildString(node, StringBuilder sb)
    • Iterative : Stack:加完root之后,先加right,再加left.
  2. deserialization :
    • divide & conquer: buildTree(Queue):
      • 把string split成array加入到queue中
        • queue.addAll(Arrays.asList(array))
      • queue pop出来的顺序就是pre-order的顺序。
      • buildTree(queue) 返回一个node值
        • pop 出#,return null
        • 由pop出的那个值,新建一个node:
          • Integer.valueOf(‘1’);
          • Integer.parseInt(‘2’);
        • 对于node的左儿子进行buildTree递归:node.left = buildTree(queue)
        • 对于node的右儿子进行buildTree递归:node.right = buildTree(queue)
    • Iterative: Stack
public class Codec {
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("#,");
return;
}
sb.append(node.val);
sb.append(",");
//当node为一个叶子节点的时候,下面的两行会在string里面加上两个##然后结束
buildString(node.left, sb);
buildString(node.right, sb);
}
public TreeNode deserialize(String data) {
String[] strs = data.split(",");
Queue queue = new LinkedList<>();
queue.addAll(Arrays.asList(strs));
return buildTree(queue);
}

private TreeNode buildTree(Queue queue){
String str = queue.poll();
if (str.equals("#")){
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(str));
//当接下来的两个都是#的时候,node为叶子节点,返回该叶子节点,
node.left = buildTree(queue);
node.right = buildTree(queue);
return node;
}
}

Pre-order Iterative:

public String serialize(TreeNode root) {
        if (root == null) return null;
        StringBuilder sb = new StringBuilder();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()){
            if (root != null) {//这里用if不用while
                sb.append(String.valueOf(root.val));
                sb.append(",");
                stack.push(root);
                root = root.left;
            }else {
                sb.append("#,");
                root = stack.pop();
                root = root.right;
            }
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) return null;
        String[] nodes = data.split(",");
        int n = nodes.length;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = new TreeNode(Integer.valueOf(nodes[0]));
        TreeNode node = root;
        stack.push(node);
        int i = 1;
        while (i < n){
            while (i < n && !nodes[i].equals("#")){
                node.left = new TreeNode(Integer.valueOf(nodes[i ++]));
                node = node.left;
                stack.push(node);
            }
            while (i < n && nodes[i].equals("#")){
                node = stack.pop();
                i ++;
            }
            
            if (i < n){
                node.right = new TreeNode(Integer.valueOf(nodes[i ++]));
                node = node.right;
                stack.push(node);
            }
        }
        return root;
    }

层遍历:BFS

serialization: Queue: non-recursive

层遍历,如果一个node为叶子节点的话,怎么继续?

  • 叶子节点的左右两个null节点应作为#.
  • 空节点的话并不再继续放null节点. 
  • 所以这样子标记的树并不是一个满的二叉树.
  • 标记满二叉树的话会Memory Limit Exceeded

serialize的时候,要记得加分隔符.因为node.val是一个int…123就不是到是1,2,3还是12,3…

deserialize的时候:不能用HashMap<Integer, TreeNode>来存新形成的node.因为树里面可能会存在两个不同的node有相同的值. 所以可以用一个TreeNode array即可.

string之间的比较一定要用equals.

难度在于,deserialization的时候如何找到当前node的左右儿子节点。

下标:

  • 在数组中,如果满二叉树(或完全二叉树)的父节点下标是 i,那么其左右孩子的下标分别为 2*i+1 和 2*i+2,
  • 若不是一个满二叉树, null节点没有左右儿子,所以后面的下标都提前了2.所以我们只需要记录每个节点前有多少个 null 节点,就可以找出该节点的孩子在哪里了,其左右孩子分别为 2*(i-num)+1 和 2*(i-num)+2(num为当前节点之前 null 节点的个数)。
  • 因为当serialization的时候我们只会把一个非空节点的左右儿子记录下来(尽管该非空节点的左右儿子可能为空)。所以整个serialization的过程记录下来的一个树,并不是一个满二叉树. 所以这里不用求树的高度.不然的话无法确定当前的空节点是否还要继续往queue里面push两个空节点. 遇到空节点直接append#就可以了.
  • 用一个TreeNode[]来存新的nodes: 这样的话第一个元素就是root,可以直接通过index来找到TreeNode,与String[]相对应,不需要再进一步查找了。

两个queue的方法. 一个queue放目前这一层的非空的node,另一个queue放下一层的node.

  • 要用到两个while loop. 里层while loop每loop一次只对当前node的左右儿子进行连接.
  • i来遍历strs.
  • 这个方法空的node不会被放入queue里面.

 

public class Codec {
 public String serialize(TreeNode root) {
 Queue<TreeNode> queue = new LinkedList<>();
 queue.offer(root);
 StringBuilder sb = new StringBuilder();
 while (!queue.isEmpty()){
 TreeNode node = queue.poll();
 if (node == null){
 sb.append("#,");
 }else {
 sb.append(node.val).append(",");
 queue.offer(node.left);
 queue.offer(node.right);
 }
 }
 return sb.toString();
 }

 // 下标法
 public TreeNode deserialize(String data) {
 String[] strs = data.split(",");
 int nullNodes = 0;
 TreeNode[] list = new TreeNode[strs.length];
 for (int i = 0; i < list.length; i ++){
 if (strs[i].equals("#")){
 list[i] = null;
 }else {
 list[i] = new TreeNode(Integer.parseInt(strs[i]));
 } }
 
 for (int i = 0; i < list.length; i ++){
 if (list[i] == null){
 nullNodes ++;
 }else {
 list[i].left = list[2 * (i - nullNodes) + 1];
 list[i].right = list[2 * (i - nullNodes) + 2];
 } }
 return list[0];
 }}

// 两个queue的方法
 public TreeNode deserialize(String data) {
 if (data == null || data.length() == 0) return null;
 String[] nodes = data.split(",");
 Queue<TreeNode> queue = new LinkedList<>();
 TreeNode root = new TreeNode(Integer.valueOf(nodes[0]));
 TreeNode node = root;
 queue.offer(node);
 int i = 1;//初始值为1,以为root自己是0,while loop里面就直接从第二个开始判断了.
 while (!queue.isEmpty()){
 Queue<TreeNode> nextQueue = new LinkedList<>();
 while (!queue.isEmpty()){
 TreeNode tmp = queue.poll();
//null node并不会被加入到queue里面.
 if (nodes[i].equals("#")) tmp.left = null;
 else {
 tmp.left = new TreeNode(Integer.valueOf(nodes[i]));
 nextQueue.offer(tmp.left);
 }
 i ++;
 if (nodes[i].equals("#")) tmp.right = null;
 else {
 tmp.right = new TreeNode(Integer.valueOf(nodes[i]));
 nextQueue.offer(tmp.right);
 }
 i ++;
 }
 queue = nextQueue;
 }
 return root;
 }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: