LintCode 7.Serialize and Deserialize Binary Tree(含测试代码)
题目描述
设计一个算法,并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”,读取文件后重建同样的二叉树被称为“反序列化”。
如何反序列化或序列化二叉树是没有限制的,你只需要确保可以将二叉树序列化为一个字符串,并且可以将字符串反序列化为原来的树结构。
样例
给出一个测试数据样例, 二叉树{3,9,20,#,#,15,7}
,表示如下的树结构:
我们的数据是进行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 }
下一篇: vue--初识