Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called 'serialization' and reading back from the file to reconstruct the exact same binary tree is 'deserialization'.
There is no limit of how you deserialize or serialize a binary tree, you only need to make sure you can serialize a binary tree to a string and deserialize this string to the original structure.
hint:
1 public class BTSerialize { 2 class TreeNode { 3 char val; 4 TreeNode left, right; 5 public TreeNode(char val) { 6 this.val = val; 7 } 8 } 9 public String serialization(TreeNode root) { 10 StringBuilder str = new StringBuilder(); 11 if (root == null) 12 return str.toString(); 13 TreeNode cur; 14 Stack stack = new Stack (); 15 stack.push(root); 16 while (!stack.isEmpty()) { 17 cur = stack.pop(); 18 if (cur.val == '#') { 19 str.append("#,"); 20 continue; 21 } 22 str.append(cur.val); 23 if (cur.left != null || cur.right != null) { 24 str.append("|"); 25 if (cur.right != null) { 26 stack.push(cur.right); 27 } else { 28 stack.push(new TreeNode('#')); 29 } 30 if (cur.left != null) { 31 stack.push(cur.left); 32 } else { 33 stack.push(new TreeNode('#')); 34 } 35 } 36 str.append(","); 37 } 38 return str.toString(); 39 } 40 41 int idx = 0; 42 public TreeNode deserialize(String data) { 43 if (data == null || data.length() == 0) return null; 44 String[] strs = data.split(","); 45 TreeNode root = null; 46 idx = 0; 47 root = helpRead(root, strs); 48 return root; 49 } 50 private TreeNode helpRead(TreeNode cur, String[] strs) { 51 if (idx >= strs.length) return null; 52 if (strs[idx].equals("#")) { 53 idx++; 54 return null; 55 } else { 56 int len = strs[idx].length(); 57 if (strs[idx].charAt(len-1) == '|') { 58 char val = strs[idx].charAt(0); 59 cur = new TreeNode(val); 60 idx++; 61 cur.left = helpRead(cur.left, strs); 62 cur.right = helpRead(cur.right, strs); 63 return cur; 64 } else { 65 char val = strs[idx].charAt(0); 66 cur = new TreeNode(val); 67 idx++; 68 return cur; 69 } 70 } 71 } 72 73 public static void main(String[] args) { 74 BTSerialize sol = new BTSerialize(); 75 TreeNode node0 = sol.new TreeNode('A'); 76 TreeNode node1 = sol.new TreeNode('B'); 77 TreeNode node2 = sol.new TreeNode('C'); 78 TreeNode node3 = sol.new TreeNode('D'); 79 TreeNode node4 = sol.new TreeNode('E'); 80 TreeNode node5 = sol.new TreeNode('F'); 81 TreeNode node6 = sol.new TreeNode('G'); 82 node0.left = node1; node0.right = node2; 83 node1.left = node3; node1.right = node4; 84 node2.left = node5; 85 node3.right = node6; 86 String str = sol.serialization(node0); 87 System.out.println(str); 88 TreeNode root = sol.deserialize(str), cur; 89 Stack stack = new Stack (); 90 stack.push(root); 91 while(!stack.isEmpty()) { 92 cur = stack.pop(); 93 System.out.print(cur.val+", "); 94 if (cur.right != null) stack.push(cur.right); 95 if (cur.left != null) stack.push(cur.left); 96 } 97 } 98 } 99 /*100 A101 / \102 B C103 / \ / 104 D E F 105 \ 106 G 107 */