题目

请实现两个函数，分别用来序列化和反序列化二叉树。

你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例：

输入：root = [1,2,3,null,null,4,5] 输出：[1,2,3,null,null,4,5]

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof

解题思路

参考1 参考2

代码实现1

 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

public class Codec {
    int INF = -2000;
    TreeNode emptyNode = new TreeNode(INF);
    public String serialize(TreeNode root) {
        if (root == null) return "";

        StringBuilder sb = new StringBuilder();
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        while (!d.isEmpty()) {
            TreeNode poll = d.pollFirst();
            sb.append(poll.val + "_");
            if (!poll.equals(emptyNode)) {
                d.addLast(poll.left != null ? poll.left : emptyNode);
                d.addLast(poll.right != null ? poll.right : emptyNode);
            }
        }
        return sb.toString();
    }

    public TreeNode deserialize(String data) {
        if (data.equals("")) return null;

        String[] ss = data.split("_");
        int n = ss.length;
        TreeNode root = new TreeNode(Integer.parseInt(ss[0]));
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        for (int i = 1; i < n - 1; i += 2) {
            TreeNode poll = d.pollFirst();
            int a = Integer.parseInt(ss[i]), b = Integer.parseInt(ss[i + 1]);
            if (a != INF) {
                poll.left = new TreeNode(a);
                d.addLast(poll.left);
            }
            if (b != INF) {
                poll.right = new TreeNode(b);
                d.addLast(poll.right);
            }
        }
        return root;
    }
}

代码实现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 Codec {
  
    
    public String serialize(TreeNode root) {
        StringBuilder sb =new  StringBuilder ();//初始化
        serialize( root, sb);
        return sb.toString();//返回字符串
      
        
    }
    public void serialize(TreeNode root,StringBuilder sb) {
        if(root==null){
            sb.append("A");//叶子节点
            return;
        }
        //先序遍历
        //1 >>>16  0 1
        //65536
        //char)(root.val) 保存8位
        sb.append("B").append((char)(root.val>>>16)).append((char)(root.val));
        serialize( root.left, sb) ;
        serialize( root.right, sb) ;

        
    }
    public int start=0;
    public TreeNode deserialize(String data) {
        if(start==data.length()){
            return null;//返回结果
        }
        if(data.charAt(start)=='A'){////叶子节点
            start++;
            return null;

        }
        TreeNode nimei =new TreeNode( ((int)data.charAt(start+1)<<16)  | ((int)data.charAt(start+2))  );//取得数据
        start+=3; //sb.append("B").append((char)(root.val>>>16)).append((char)(root.val));
        nimei.left=deserialize(data);
        nimei.right=deserialize(data);
        return nimei;
    }
}