描述

剑指offer JZ37 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）

二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

方法一：使用队列，通过层序遍历来序列化和

思路：
1.序列化二叉树
将根节点的值加入字符串，将根节点的左节点以及右节点分别入队，循环知道遍历所有节点。
2.反序列化二叉树
同样使用队列，将字符串中的值依此取出，创造节点，找到其父节点建立关系，并且放入队列中，依此类推。
代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 public class Solution {
    String Serialize(TreeNode root) {
        StringBuffer stringBuffer =  new StringBuffer();
        if (root == null) return stringBuffer.toString();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                stringBuffer.append("#,");
                continue;
            }
            else stringBuffer.append(node.val + ",");
            queue.offer(node.left);
            queue.offer(node.right);
        }
        return stringBuffer.toString();

    }
    
    TreeNode Deserialize(String str) {
       String[] strs = str.split(",");
       if (strs.length == 1) return null;
       Queue<TreeNode> queue = new LinkedList<>();
       int index = 0;
       TreeNode root = new TreeNode(Integer.parseInt(strs[index++]));
       queue.offer(root);
       while (index < strs.length) {
        TreeNode node = queue.poll();
        if (node == null) {
            continue;
        }
        String str1 = strs[index++];
        String str2 = strs[index++];
        if (str1.equals("#")) {
            node.left = null;
            queue.offer(null);
        } else {
            TreeNode leftNode = new TreeNode(Integer.parseInt(str1));
            node.left = leftNode;
            queue.offer(leftNode);
        }
        if (str2.equals("#")) {
            node.right = null;
            queue.offer(null);
        } else {
            TreeNode rightNode = new TreeNode(Integer.parseInt(str2));
            node.right = rightNode;
            queue.offer(rightNode);
        }
       }
       return root;


    }
       
}

方法二：前序遍历递归实现

思路：
1.序列化二叉树
通过前序遍历递归将二叉树依次转化为字符串
2.反序列化二叉树
通过前序遍历递归将二叉树依次转化为节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Solution {
    public static int index = 0;
    void tranverseSerialize(TreeNode node, StringBuffer sb) {
        if (node == null) sb.append("#,");
        else{
            sb.append(node.val + ",");
            tranverseSerialize(node.left, sb);
            tranverseSerialize(node.right, sb);
        }
        
    }


    String Serialize(TreeNode root) {
        StringBuffer stringBuffer =  new StringBuffer();
        if (root == null) return stringBuffer.toString();
        tranverseSerialize(root, stringBuffer);
        return stringBuffer.toString();
    }

    TreeNode tranverseDeserialize(String[] strs) {
        if (strs[index].equals("#")) {
            index++;
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(strs[index++]));
        if (index == strs.length) return node;
        node.left = tranverseDeserialize(strs);
        node.right = tranverseDeserialize(strs);
        return node;
        
    }
    
    TreeNode Deserialize(String str) {
       String[] strs = str.split(",");
       if (strs.length == 1) return null;
    
       
       return tranverseDeserialize(strs);


    }
       
}