leetcode449. 序列化和反序列化二叉搜索树

leetcode449. 序列化和反序列化二叉搜索树

三月 22, 2020

leetcode449. 序列化和反序列化二叉搜索树

序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

设计一个算法来序列化和反序列化二叉搜索树。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。

编码的字符串应尽可能紧凑。

注意：不要使用类成员/全局/静态变量来存储状态。 你的序列化和反序列化算法应该是无状态的。

我的思路

我的思路很直接,开始的写法没有注意到二叉搜索树还原后要与原来一样,所以中序遍历不对.然后我尝试用层序遍历写.

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null)return new String();
        StringBuffer sbf=new StringBuffer();
        Queue<TreeNode>queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode node=queue.poll();
                if(node==null){
                    sbf.append("null,");
                    continue;
                }
                sbf.append(String.valueOf(node.val));
                sbf.append(",");
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        //sbf.delete(sbf.length()-1,sbf.length());
        //System.out.println(sbf);
        return new String(sbf);
    }
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.length()==0)return null;
        StringBuffer sbf=new StringBuffer(data);
        Queue<TreeNode>queue=new LinkedList<>();
       
        int index=sbf.indexOf(",");
        String sub=sbf.substring(0,index);
        sbf=sbf.delete(0,index+1);
        TreeNode root=new TreeNode(Integer.valueOf(sub));
        queue.offer(root);
        
        int level=0;
        while(!queue.isEmpty()){
            int count=1<<level;
            int size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode node=queue.poll();
                if(node==null)continue;
                
                    index=sbf.indexOf(",");
                    sub=sbf.substring(0,index);
                    sbf=sbf.delete(0,index+1);
                    if(sub.equals("null")){
                        node.left=null;
                    }else{
                        node.left=new TreeNode(Integer.valueOf(sub));
                    }
                    queue.offer(node.left);

                    index=sbf.indexOf(",");
                    sub=sbf.substring(0,index);
                    sbf=sbf.delete(0,index+1);
                    if(sub.equals("null")){
                        node.right=null;
                    }else{
                        node.right=new TreeNode(Integer.valueOf(sub));
                    }
                    
                    queue.offer(node.right);
                
            }
        }
       return root;
    }
    
}

序列化和反序列化都是层序遍历.

题解区解法:利用二叉搜索树的性质

java使用前序遍历完成序列化和反序列化
因而二叉搜索树知道中序遍历,如果一开始用前序遍历,就相当于已知两个遍历,就能确定一颗树.

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
class Codec {
    // Encodes a tree to a single string.
    //BST的前序遍历结果
    public String serialize(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        helper(root, sb);
        return sb.substring(0, sb.length() - 1);
    }

    private void helper(TreeNode root, StringBuilder sb) {
        if (root == null) return;
        //拼接当前节点
        sb.append(root.val).append(",");
        helper(root.left, sb);
        helper(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) return null;
        String[] arr = data.split(",");
        return builder(arr, 0, arr.length - 1);
    }

    private TreeNode builder(String[] arr, int lo, int hi) {
        if (lo > hi) return null;
        TreeNode root = new TreeNode(Integer.valueOf(arr[lo]));
        //找到第一个比首元素大的元素位置
        int index = hi + 1;
        for (int i = lo + 1; i <= hi; i++) {
            if (Integer.valueOf(arr[i]) > root.val) {
                index = i;
                break;
            }
        }
        //递归构建子树
        root.left = builder(arr, lo + 1, index - 1);
        root.right = builder(arr, index, hi);
        return root;
    }
}

通用解法

只用先序遍历,不过编码需要注意,在当前节点为null时,需要编码为”null,”,这样就可以只用先序遍历构造一棵树.来源于297题官方题解

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
public class Codec {
    // Encodes a tree to a single string.
  public String serialize(TreeNode root) {
    StringBuffer sbf=new StringBuffer();
    rserialize(root, sbf);
    return new String(sbf);
  }
  public void rserialize(TreeNode root, StringBuffer str) {
    // Recursive serialization.
    if (root == null) {
      str.append("null,");
    } else {
        str.append(String.valueOf(root.val));
        str.append(",");
        rserialize(root.left, str);
        rserialize(root.right, str);
    }
  }

  // Decodes your encoded data to tree.
  public TreeNode deserialize(String data) {
    String[] data_array = data.split(",");
    List<String> data_list = new LinkedList<String>(Arrays.asList(data_array));
    return rdeserialize(data_list);
  }
  public TreeNode rdeserialize(List<String> l) {
    // Recursive deserialization.
    if (l.get(0).equals("null")) {
      l.remove(0);
      return null;
    }
    TreeNode root = new TreeNode(Integer.valueOf(l.get(0)));
    l.remove(0);
    root.left = rdeserialize(l);
    root.right = rdeserialize(l);
    return root;
  }
}

leetcode 59/100