Binary Tree Serialization

Basic idea is to use a symbol to represent null node. it can be any traversal order implementation wise. below is one with DFS pre-order traversal

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.

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

/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ //I will use DFS to serielize and deserielize the tree //use # to represent null node class Solution { /** * This method will be invoked first, you should design your own algorithm * to serialize a binary tree which denote by a root node to a string which * can be easily deserialized by your own "deserialize" method later. */ public String serialize(TreeNode root) { // write your code here StringBuilder sb = new StringBuilder(); dfsBuildString(root, sb); sb.deleteCharAt(sb.length()-1);//remove last , return sb.toString(); } private void dfsBuildString(TreeNode node, StringBuilder sb) { if (node == null) { sb.append("#,"); } else { sb.append(node.val + ",");//pre order dfsBuildString(node.left, sb);//left dfsBuildString(node.right,sb);//right } } /** * This method will be invoked second, the argument data is what exactly * you serialized at method "serialize", that means the data is not given by * system, it's given by your own serialize method. So the format of data is * designed by yourself, and deserialize it here as you serialize it in * "serialize" method. */ public TreeNode deserialize(String data) { if(data==null||data.length()==0)return null; // write your code here Queue<String> nodes = new LinkedList<String>(); nodes.addAll(Arrays.asList(data.split(","))); return dfsBuildTree(nodes); } private TreeNode dfsBuildTree(Queue<String> nodes) { String val = nodes.remove();//using queue to easily remove nodes if (val.equals("#")) return null; TreeNode node = new TreeNode(Integer.valueOf(val));//build a root node node.left = dfsBuildTree(nodes);///build left node.right = dfsBuildTree(nodes);//build right tree return node; } }