297.Serialize-and-Deserialize-Binary-Tree
297. Serialize and Deserialize Binary Tree
题目地址
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.
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.代码
Approach 1: Depth First Search (DFS)
/**
* 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) {
return preorder(root, "");
}
public String preorder(TreeNode root, String str) {
if (root == null) {
str += "null,";
} else {
str += str.valueOf(root.val) + ",";
str = preorder(root.left, str);
str = preorder(root.right, str);
}
return str;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] data_array = data.split(",");
List<String> data_list = new LinkedList<String>(Arrays.asList(data_array));
return rdeserialize(data_list);
}
public TreeNode rdeserialize(List<String> l) {
if (l.get(0).equals("null")) {
l.remove(0);
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(l.get(0)));
l.remove(0);
root.left = rdeserialize(l);
root.right = rdeserialize(l);
return root;
}
}Approach #2 Iterative Preorder DFS
class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
Deque<TreeNode> stack = new LinkedList<>();
while (root != null || !stack.isEmpty()) {
if (root != null) {
sb.append(String.valueOf(root.val) + ",");
stack.push(root); // 压入已访问的root
root = root.left;
} else {
sb.append("null,");
root = stack.pop();
root = root.right;
}
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.length() == 0) return null;
String[] data_array = data.split(",");
Queue<String> data_list = new LinkedList<String>(Arrays.asList(data_array));
Deque<TreeNode> stack = new LinkedList<>();
TreeNode root = new TreeNode(Integer.valueOf(data_list.poll()));
TreeNode x = root;
stack.push(x);
while (!data_list.isEmpty()) {
// left
while (!data_list.peek().equals("null")) {
x.left = new TreeNode(Integer.valueOf(data_list.poll()));
x = x.left;
stack.push(x); // 压入已访问的 x.left
}
// equal null
while (!data_list.isEmpty() && data_list.peek().equals("null")) {
x = stack.pop();
data_list.poll();
}
// right
if (!data_list.isEmpty()) {
x.right = new TreeNode(Integer.valueOf(data_list.poll()));
x = x.right;
stack.push(x);
}
}
return root;
}
}Approach #3 BFS Preorder
class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return "";
Queue<TreeNode> q = new LinkedList<>();
StringBuilder sb = new StringBuilder();
q.offer(root);
sb.append(String.valueOf(root.val) + ",");
while (!q.isEmpty()) {
TreeNode node = q.poll();
if (node.left == null) {
sb.append("null,");
} else {
q.offer(node.left);
sb.append(String.valueOf(node.left.val) + ",");
}
if (node.right == null) {
sb.append("null,");
} else {
q.offer(node.right);
sb.append(String.valueOf(node.right.val) + ",");
}
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String str) {
if (str.length() == 0) return null;
String[] data_array = str.split(",");
Queue<String> data_list = new LinkedList<String>(Arrays.asList(data_array));
Queue<TreeNode> q = new LinkedList<>();
TreeNode root = new TreeNode(Integer.valueOf(data_list.poll()));
q.offer(root);
while (!q.isEmpty()) {
TreeNode node = q.poll();
// left
if (data_list.peek().equals("null")) {
node.left = null;
} else {
node.left = new TreeNode(Integer.valueOf(data_list.peek()));
q.offer(node.left);
}
data_list.poll();
// right
if (data_list.peek().equals("null")) {
node.right = null;
} else {
node.right = new TreeNode(Integer.valueOf(data_list.peek()));
q.offer(node.right);
}
data_list.poll();
}
return root;
}
}Approach #3 Postorder traversal to optimise space for the tree structure
public class Codec {
public StringBuilder postorder(TreeNode root, StringBuilder sb) {
if (root == null) return sb;
postorder(root.left, sb);
postorder(root.right, sb);
sb.append(root.val);
sb.append(' ');
return sb;
}
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = postorder(root, new StringBuilder());
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.isEmpty()) return null;
ArrayDeque<Integer> nums = new ArrayDeque<Integer>();
for (String s : data.split("\\s+"))
nums.add(Integer.valueOf(s));
return helper(Integer.MIN_VALUE, Integer.MAX_VALUE, nums);
}
public TreeNode helper(Integer lower, Integer upper, ArrayDeque<Integer> nums) {
if (nums.isEmpty()) return null;
int val = nums.getLast();
if (val < lower || val > upper) return null;
nums.removeLast();
TreeNode root = new TreeNode(val);
root.right = helper(val, upper, nums);
root.left = helper(lower, val, nums);
return root;
}
}Approach #3 Get rid of delimiters
public class Codec {
// Encodes a tree to a list.
public void postorder(TreeNode root, StringBuilder sb) {
if (root == null) return;
postorder(root.left, sb);
postorder(root.right, sb);
sb.append(intToString(root.val));
}
// Encodes integer to bytes string
public String intToString(int x) {
char[] bytes = new char[4];
for(int i = 3; i > -1; --i) {
bytes[3 - i] = (char) (x >> (i * 8) & 0xff);
}
return new String(bytes);
}
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
postorder(root, sb);
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
ArrayDeque<Integer> nums = new ArrayDeque<Integer>();
int n = data.length();
for(int i = 0; i < (int)(n / 4); ++i) {
nums.add(stringToInt(data.substring(4 * i, 4 * i + 4)));
}
return helper(Integer.MIN_VALUE, Integer.MAX_VALUE, nums);
}
// Decodes list to tree.
public TreeNode helper(Integer lower, Integer upper, ArrayDeque<Integer> nums) {
if (nums.isEmpty()) return null;
int val = nums.getLast();
if (val < lower || val > upper) return null;
nums.removeLast();
TreeNode root = new TreeNode(val);
root.right = helper(val, upper, nums);
root.left = helper(lower, val, nums);
return root;
}
// Decodes bytes string to integer
public int stringToInt(String bytesStr) {
int result = 0;
for(char b : bytesStr.toCharArray()) {
result = (result << 8) + (int)b;
}
return result;
}
}Last updated