Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
Example:
You may serialize the following tree: 1 / \ 2 3 / \ 4 5 as "[1,2,3,null,null,4,5]"Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
思路：
1. To serialize, maintain a StringBuilder, using dfs to preorder traversal the tree
(1) if node is null, StringBuilder append ("#") and a splitter(",")
(2)otherwise, StringBuilder append (root.val) and a splitter(",")
2. To deserialize, mainatain a queue containing each node informaton, using corresponding preorder traversal to build a tree
代码：
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Codec { 11 // Encodes a tree to a single string. 12 public String serialize(TreeNode root) { 13 StringBuilder sb = new StringBuilder(); 14 buildString(root, sb); 15 return sb.toString(); 16 } 17 18 private void buildString(TreeNode root, StringBuilder sb){ 19 if(root == null){ 20 sb.append("#").append(","); 21 }else{ 22 // I use pre-order traversal: root, left, right 23 sb.append(root.val).append(","); 24 buildString(root.left, sb); 25 buildString(root.right, sb); 26 } 27 } 28 29 // Decodes your encoded data to tree. 30 public TreeNode deserialize(String data) { 31 if(data == null) return null; 32 String[]strArr = data.split(","); 33 Queue<String> queue = new LinkedList<>(); 34 // put each item of strArr into queue 35 Collections.addAll(queue, strArr); 36 return buildTree(queue); 37 } 38 39 private TreeNode buildTree(Queue<String> queue){ 40 if(queue.isEmpty()) return null; 41 String s = queue.poll(); 42 if(s.equals("#")) return null; 43 // to match serialize pre-order traversal 44 TreeNode root = new TreeNode(Integer.parseInt(s)); 45 root.left = buildTree(queue); 46 root.right = buildTree(queue); 47 return root; 48 } 49 } 50 51 // Your Codec object will be instantiated and called as such: 52 // Codec codec = new Codec(); 53 // codec.deserialize(codec.serialize(root));
转载于:https://www.cnblogs.com/liuliu5151/p/9808265.html
