297. Serialize and Deserialize Binary Tree (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.
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.
Solutions
class Codec {
// The most crucial stuff is how we define the visiting path, here we will take a
// simple string as an example to demonstrate. For node N, the path expression is
// "lllr", which denotes the sequence of nodes we take and it can be interpreted as
// step 1. move left; step 2. move left; step 3. move left; step 4. move right.
// Solution A
// 1. Sort the max depth of tree n.
// 2. Define an array (2^n)-1 initialized with null
// 3. Recurse the tree nodes and work out the corresponding index of each node
// in above array in light of the path, then set the node value
// Solution B
// 1. Define a List which is used to keep the unique path toward specific node.
// 2. Recurse the tree nodes and combine the visiting path and node value, then store
// it to above List. The combination looks like "llr=n", where l and r are
// direction of branch; represents the link between two nodes; = signifies the separator
// between path and node value.
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "";
}
List<String> nodePaths = new ArrayList<>();
recurse(root, "", nodePaths);
String ans = "";
for (String path : nodePaths) {
ans += path + " ";
}
return ans.trim();
}
private void recurse(TreeNode node, String path, List<String> nodePaths) {
if (node == null) {
return;
}
// remove prefix '>'
nodePaths.add(path + "#" + node.val);
recurse(node.left, path + "l", nodePaths);
recurse(node.right, path + "r", nodePaths);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
TreeNode root = null;
String[] nodeStrs = data.split(" ");
for (String str : nodeStrs) {
String path = str.split("#")[0];
int val = Integer.valueOf(str.split("#")[1]);
if (path == null || path.length() == 0) {
root = new TreeNode(val);
continue;
}
TreeNode tmp = root;
for (int i = 0; i < path.length(); i++) {
int c = path.charAt(i);
if (i == path.length() - 1) {
if (c == 'l') {
tmp.left = new TreeNode(val);
} else {
tmp.right = new TreeNode(val);
}
break;
}
if (path.charAt(i) == 'l') {
tmp = tmp.left;
} else {
tmp = tmp.right;
}
}
}
return root;
}
}