[LeetCode] Serialize and Deserialize Binary Tree
文章目录
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.
DFS
Time Complexity
serialize:O(N)
deserialize: O(N)
Space Complexity
O(N)
思路
Use preorder to serialize the tree, use "n" to denote null node and split node with ",". We can use a stringBuilder to build the string.
Use preorder to deserialize the tree, because we want to get the value from the start of the string one by one, which is like a queue. So we put the string into queue, then poll the value out as the node of the string.
代码
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
//corner case
if(root == null) return "";
StringBuilder sb = new StringBuilder();
helper(root, sb);
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}
private void helper(TreeNode root, StringBuilder sb){
if(root == null){
sb.append("n").append(",");
return;
}
sb.append(root.val).append(",");
helper(root.left, sb);
helper(root.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data == null || data.length() == 0) return null;
Queue<String> queue = new LinkedList<>();
queue.addAll(Arrays.asList(data.split(",")));
return helper(queue);
}
private TreeNode helper(Queue<String> queue){
//base case
String val = queue.poll();
if(val.equals("n")) return null;
TreeNode root = new TreeNode(Integer.valueOf(val));
root.left = helper(queue);
root.right = helper(queue);
return root;
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论