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.
Constraints:
- The number of nodes in the tree is in the range [0, 10^4].
- The value of each node is unique and is in the range [0, 10^8].
Examples:
Input: [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
Explanation: For example, the above binary tree is serialized as [1,2,3,null,null,4,5], which means the value of the root node is 1, the value of the left child of the root node is 2, the value of the right child of the root node is 3, and so on.
Solutions
Depth-First Search (DFS)
The provided solution uses a depth-first search (DFS) approach to serialize and deserialize the binary tree. The serialize function traverses the tree in a pre-order manner (root, left, right) and appends the node values to a string. If a node is null, it appends 'X' to the string. The deserialize function splits the input string into an array of node values and reconstructs the tree using a recursive DFS approach.
class Codec {
public: string serialize(TreeNode* root) {
string data;
serializeHelper(root, data);
return data;
}
void serializeHelper(TreeNode* node, string& data) {
if (!node) {
data += "X,";
return;
}
data += to_string(node->val) + ",";
serializeHelper(node->left, data);
serializeHelper(node->right, data);
}
TreeNode* deserialize(string data) {
stringstream ss(data);
string node;
int index = 0;
return deserializeHelper(ss, node, index);
}
TreeNode* deserializeHelper(stringstream& ss, string& node, int& index) {
if (index >= data.size() || node == "X") {
index++;
return nullptr;
}
TreeNode* newNode = new TreeNode(stoi(node));
index++;
deserializeHelper(ss, node, index);
deserializeHelper(ss, node, index);
return newNode;
}
}Follow-up:
How would you optimize the serialization and deserialization process for a very large binary tree?
