Hard
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
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 5as
"[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.
Deserialize: String 转成 Binary Tree
思路: use 2 string marker: "X" for null - empty node, "," for spliter - spliting nodes
To Serialize, do pre-order traversal. Append node.val(sb可直接append数字) + spliter to StringBuilder recursively.
To Deserialize, create a queue to add nodes from string(need to 1st split 2nd convert to arraylist) . Then recursively build the tree by pointing left & right children.
Complexity: O(N) time travel all nodes
public class Codec { private final String nullN = "X"; private final String spliter = ","; // Encodes a tree to a single string. public String serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); buildString(root,sb); return sb.toString(); } private void buildString(TreeNode node, StringBuilder sb){ if(node == null){ sb.append(nullN).append(spliter); return; } sb.append(node.val).append(spliter); buildString(node.left,sb); buildString(node.right,sb); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { Queue<String> nodes = new LinkedList<String>(); nodes.addAll(Arrays.asList(data.split(spliter))); return buildTree(nodes); } private TreeNode buildTree(Queue<String> nodes){ String val = nodes.remove();//return null if(val.equals(nullN)) return null; TreeNode node = new TreeNode (Integer.valueOf(val));//Integer.parseInt() node.left = buildTree(nodes); node.right = buildTree(nodes); return node; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.deserialize(codec.serialize(root));
No comments:
Post a Comment