欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LintCode 7.Serialize and Deserialize Binary Tree(含测试代码)

程序员文章站 2022-04-10 15:20:11
题目描述 设计一个算法,并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”,读取文件后重建同样的二叉树被称为“反序列化”。 如何反序列化或序列化二叉树是没有限制的,你只需要确保可以将二叉树序列化为一个字符串,并且可以将字符串反序列化为原来的树结构。 样例 给出一个测试数据样例, 二 ......

题目描述

设计一个算法,并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”,读取文件后重建同样的二叉树被称为“反序列化”。

如何反序列化或序列化二叉树是没有限制的,你只需要确保可以将二叉树序列化为一个字符串,并且可以将字符串反序列化为原来的树结构。

样例

给出一个测试数据样例, 二叉树{3,9,20,#,#,15,7},表示如下的树结构:

LintCode 7.Serialize and Deserialize Binary Tree(含测试代码)

我们的数据是进行BFS遍历得到的。当你测试结果wrong answer时,你可以作为输入调试你的代码。你可以采用其他的方法进行序列化和反序列化。


 

在编程过程中,采用Queue队列结构来保存树节点,因此有必要熟悉一下Queue接口(Deque接口是Queue接口的子接口,代表一个双端队列)的相关知识点。

1.Queue接口与List、Set属于同一级别,都是继承了Collection接口。LinkedList类实现了Queue接口,因此我们可以把LinkedList当成Queue来用。

2.Queue使用时要尽量避免Collection的add()和remove()方法,而是要使用offer()来加入元素,使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否,而add()和remove()方法在失败的时候会抛出异常。

 

另外要用到字符串结构,需弄明白 String, StringBuilder 以及 StringBuffer 这三个类之间有什么区别?

1.首先说运行速度,或者说是执行速度,在这方面运行速度快慢为:StringBuilder > StringBuffer > String

  String最慢的原因:

  String为字符串常量,而StringBuilder和StringBuffer均为字符串变量,即String对象一旦创建之后该对象是不可更改的,但后两者的对象是变量,是可以更改的。

2. 再来说线程安全

  在线程安全上,StringBuilder是线程不安全的,而StringBuffer是线程安全的。

因此:
  String:适用于少量的字符串操作的情况

  StringBuilder:适用于单线程下在字符缓冲区进行大量操作的情况

  StringBuffer:适用多线程下在字符缓冲区进行大量操作的情况

 

实现代码:

  1 import java.util.LinkedList;
  2 import java.util.Queue;
  3 
  4 class TreeNode {
  5     public int val;//节点的值
  6     public TreeNode left,right;//左右节点
  7     public TreeNode(int val){
  8         this.val = val;//初始化节点
  9         this.left = this.right = null;
 10     }
 11 }
 12 
 13 public class SerializeTree {
 14     public static void main(String[] args) throws Exception {
 15         TreeNode node1 = new TreeNode(3);
 16         TreeNode node2 = new TreeNode(9);
 17         TreeNode node3 = new TreeNode(20);
 18         node1.left = node2;
 19         node1.right = node3;
 20         TreeNode node4 = new TreeNode(15);
 21         TreeNode node5 = new TreeNode(7);
 22         node3.left = node4;
 23         node3.right = node5;
 24         
 25         String s = new SerializeTree().serialize(node1);
 26         System.out.println(s);
 27         
 28         String str = new String("3,9,20,#,#,15,7");
 29         //TreeNode root = new SerializeTree().deserialize(s);
 30         TreeNode root = new SerializeTree().deserialize(str);
 31         System.out.println((int)root.val);
 32         System.out.println(root.left.val);
 33         System.out.println(root.right.val);
 34         
 35         
 36     }
 37     
 38     /*将一棵树序列化一个字符串*/
 39     public String serialize(TreeNode root) {
 40         Queue<TreeNode> queue = new LinkedList<>();
 41         StringBuffer sb = new StringBuffer();
 42         
 43         queue.offer(root);
 44         while(!queue.isEmpty()) {
 45             TreeNode data = queue.poll();
 46             if(data != null) {
 47                 sb.append(data.val+",");
 48                 queue.offer(data.left);
 49                 queue.offer(data.right);
 50             }
 51             else
 52                 sb.append("#,");
 53         }
 54         //return sb.toString();
 55         return sb.substring(0, sb.length()-1);//去掉字符串末尾的“,”号
 56     }
 57     
 58     /*将一个字符串反序列化为一棵树*/
 59     public TreeNode deserialize(String data) throws Exception {
 60         Queue<TreeNode> queue = new LinkedList<>();
 61         String string = data.substring(0, data.length());
 62         String[] s = string.split(",");
 63         /*for(int i =0;i<s.length-1;i++) {
 64             System.out.print(s[i]+" ");
 65         }
 66         System.out.println(s[s.length-1]);*/
 67         int i = 0;
 68         if(s[i].equals("#")) 
 69             return null;
 70         
 71         TreeNode root = new TreeNode(Integer.parseInt(s[i]));
 72         queue.offer(root);
 73         
 74         while(!queue.isEmpty() && i < s.length-1 )  {
 75             i++;
 76             TreeNode tmp = queue.poll();
 77             
 78                 if(s[i].equals("#")) {
 79                     
 80                     tmp.left = null;
 81                 }
 82             else
 83             {
 84                 TreeNode left = new TreeNode(Integer.parseInt(s[i]));
 85                 tmp.left = left;
 86                 queue.offer(left);
 87             }
 88             
 89             i++;
 90             if(s[i].equals("#"))
 91                 tmp.right = null;
 92             else 
 93             {
 94                 TreeNode right = new TreeNode(Integer.parseInt(s[i]));
 95                 tmp.right = right;
 96                 queue.offer(right);
 97             }
 98         }
 99         return root;
100     }
101         
102 }