If you’re not familiar with data structures, take a look: A swastika explanation of data structures
Reference to Offer series
Brush question warehouse
37. Serialize binary trees
Topic describes
Implement two functions to serialize and deserialize the binary tree
The serialization of binary tree means that the result of a binary tree traversed in a certain way is saved as a string in a certain format, so that the binary tree built in memory can be persisted. Serialization can be modified based on a binary tree traversal of order first, middle, last, and layer. The result of serialization is a string, denoted by some symbol for the empty node (#), starting with! Denotes the end of a node value (value!). .
Deserialization of binary tree is to reconstruct the binary tree according to the serialized string STR obtained in a certain traversal order.
For example, we could serialize a binary tree with only a root node of 1 as “1,” and then parse back to the binary tree example 1 through our own function
The input
,6,10,5,7,9,11 {8}
The return value
,6,10,5,7,9,11 {8}
Ideas & Solutions
Serialization: Make the call sequential traversal, that is, traversal the root node, then left, left, and right nodes, using recursion. If it is empty, it is replaced by “#” and separated by “, “.
Deserialization: split by comma, using index as index, +1 each time, again using recursion, first root node, then left node, then right node.
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
int index = -1;
String Serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
if(root == null) {
sb.append(# ",");
return sb.toString();
}
sb.append(root.val + ",");
sb.append(Serialize(root.left));
sb.append(Serialize(root.right));
return sb.toString();
}
TreeNode Deserialize(String str) {
index++;
String[] strs = str.split(",");
TreeNode node = null;
if(! strs[index].equals("#")) {
node = new TreeNode(Integer.valueOf(strs[index]));
node.left = Deserialize(str);
node.right = Deserialize((str));
}
returnnode; }}Copy the code
The C++ code is as follows:
class Solution {
public:
char *Serialize(TreeNode *root) {
if(! root) {return "#";
}
string res = to_string(root->val);
res.push_back(', ');
char *left = Serialize(root->left);
char *right = Serialize(root->right);
char *ret = new char[strlen(left) + strlen(right) + res.size()];
strcpy(ret, res.c_str());
strcat(ret, left);
strcat(ret, right);
return ret;
}
TreeNode *deseri(char *&str) {
if (*str == The '#') {
++str;
return nullptr;
}
int num = 0;
while(*str ! =', ') {
num = num * 10 + (*str - '0');
++str;
}
++str;
TreeNode *root = new TreeNode(num);
root->left = deseri(str);
root->right = deseri(str);
return root;
}
TreeNode *Deserialize(char *str) {
return deseri(str); }};Copy the code
[Author profile] : Qin Huai, public number [Qin Huai grocery store] author, personal website: aphysia.cn, the road of technology is not at that time, mountain high water long, even if slow, chi and not stop.
Offer all questions in PDF
Open Source Programming Notes