description: 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.
For example, you may serialize the following tree
1 / \ 2 3 / \ 4 5
as “[1,2,3,null,null,4,5]”, just the same as how LeetCode OJ 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
这个题目，一共用了将近3个小时，各种小bug层出不穷。但好在最后总算是解决了。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { if (root == null) { return "[]"; } StringBuffer sb = new StringBuffer(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); List<TreeNode> list = new ArrayList<>(); while(!queue.isEmpty()) { TreeNode node = queue.poll(); list.add(node); if (node == null) { continue; } queue.offer(node.left); queue.offer(node.right); } while(list.get(list.size() - 1) == null) { list.remove(list.size() - 1); } sb.append("["); for (TreeNode nodex : list) { if (nodex == null) { sb.append("null,"); } else { sb.append(nodex.val + ","); } } sb.deleteCharAt(sb.length() - 1); sb.append("]"); System.out.println(sb.toString()); return sb.toString(); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if ("[]".equals(data)) { return null; } String[] arr = data.substring(1, data.length() - 1).split("[,]"); int index = 0; TreeNode root = new TreeNode(Integer.parseInt(arr[0])); List<TreeNode> list = new ArrayList<>(); list.add(root); boolean isLeft = true; for (int i = 1; i < arr.length; i++) { if (!arr[i].equals("null")) { TreeNode node = new TreeNode(Integer.parseInt(arr[i])); list.add(node); if (isLeft) { list.get(index).left = node; } else { list.get(index).right = node; } } if (!isLeft) { index++; } isLeft = !isLeft; } return root; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.deserialize(codec.serialize(root));