LeetCode 297. Serialize and Deserialize Binary Tree

原题链接在这里：https://leetcode.com/problems/serialize-and-deserialize-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.

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.

For example, you may serialize the following tree

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ 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.

题解：

把一个树serialize 和 deserialize. 可以通过pre-order 或者 level order traversal.

用pre-order:

例子就变成了"1,2,#,#,3,4,#,#,5,#,#". 然后deserialize先读入一个字符作为根节点，然后根节点的左右子节点递归调用deserializeHelper函数.

deserialize 时按"," 拆开，遇到"#"就是 null节点.

Note: LinkedList AddAll only works for Collection<>, array is not Collection<>. Thus it needs to use Arrays.asList(arr).

Time Complexity: serialize, O(n). deserialize, O(n). Space: O(n).

AC Java:

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Codec {
11     
12     // Encodes a tree to a single string.
13     public String serialize(TreeNode root) {
14         StringBuilder sb = new StringBuilder();
15         preorder(root, sb);
16         return sb.toString();
17     }
18     private void preorder(TreeNode root, StringBuilder sb){
19         if(root == null){
20             sb.append("#").append(",");
21             return;
22         }
23         sb.append(root.val).append(",");
24         preorder(root.left, sb);
25         preorder(root.right, sb);
26     }
27 
28     // Decodes your encoded data to tree.
29     public TreeNode deserialize(String data) {
30         LinkedList<String> que = new LinkedList<String>();
31         que.addAll(Arrays.asList(data.split(",")));
32         return deserial(que);
33     }
34     
35     private TreeNode deserial(LinkedList<String> que){
36         String str = que.pollFirst();
37         if(str.equals("#")){
38             return null;
39         }
40         TreeNode root = new TreeNode(Integer.valueOf(str));
41         root.left = deserial(que);
42         root.right = deserial(que);
43         return root;
44     }
45 }
46 
47 // Your Codec object will be instantiated and called as such:
48 // Codec codec = new Codec();
49 // codec.deserialize(codec.serialize(root));

Iteration 方法使用的BFS. 当处理serialize, queue不为空时，弹出节点cur, 若cur是null, 就在sb后面加上"#,"; 若不是null, 就在sb后面加上cur.val 和 ",".

处理deserialize时，先把string 用"," 格成string 数组。如果是满树，那么左节点index就是2*i+1, 右节点index是2*i+2. 但这里不是满树。

需要同时记录当前i前面有几个null节点，用count存储，左节点index变成2*(i-count[i]) + 1, 右节点index变成2*(i-count[i]) + 2.

Note: 记住Queue 是 abstract class, 不能直接用来生成 que, 需要用LinkedList.

AC Java:

 1 public class Codec {
 2 
 3     // Encodes a tree to a single string.
 4     public String serialize(TreeNode root) {
 5         StringBuilder sb = new StringBuilder();
 6         Queue<TreeNode> que = new LinkedList<TreeNode>(); //error
 7         que.offer(root);
 8         while(!que.isEmpty()){
 9             TreeNode cur = que.poll();
10             if(cur == null){
11                 sb.append("#,");
12             }else{
13                 sb.append(cur.val).append(",");
14                 que.offer(cur.left);
15                 que.offer(cur.right);
16             }
17         }
18         return sb.toString();
19     }
20 
21     // Decodes your encoded data to tree.
22     public TreeNode deserialize(String data) {
23         String [] s = data.split(",");
24         int [] count = new int[s.length];
25         TreeNode [] tns = new TreeNode[s.length];
26         
27         for(int i = 0; i<s.length; i++){
28             if(i>0){
29                 count[i] = count[i-1];
30             }
31             if(s[i].equals("#")){
32                 tns[i] = null;
33                 count[i]++;
34             }else{
35                 tns[i] = new TreeNode(Integer.valueOf(s[i]));
36             }
37         }
38         
39         for(int i = 0; i<s.length; i++){
40             if(s[i].equals("#")){
41                 continue;
42             }
43             tns[i].left = tns[2 * (i-count[i]) + 1];
44             tns[i].right = tns[2 * (i-count[i]) + 2];
45         }
46         return tns[0];
47     }
48 }

类似Find Duplicate Subtrees.

Reference: http://blog.csdn.net/ljiabin/article/details/49474445

LeetCode 297. Serialize and Deserialize Binary Tree

相关推荐