Description
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.
Clarification: The input/output 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.
Examples:
Example 1:
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
Example 2:
Input: root = []
Output: []Solution in Python
To serialize and deserialize a binary tree, we’ll use a pre-order traversal approach. Pre-order traversal processes the root node first, then recursively processes the left subtree followed by the right subtree. This method will allow us to store the structure of the tree in a string and reconstruct it from the same string.
Serialization:
- Serialize: We will convert the binary tree into a string representation using a pre-order traversal. During the traversal, we will record node values as strings and use a marker (e.g.,
#) to denotenullnodes (representing the absence of children). The values will be separated by commas.
Deserialization:
- Deserialize: We will take the serialized string, split it by commas to get a list of node values, and then reconstruct the tree using the same pre-order approach. We will treat each value, either as a valid node or a
nullmarker, to build the tree recursively.
Python
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
# Helper function for pre-order traversal to serialize the tree
def helper(node):
if node is None:
return "#," # Use '#' to represent a null node
# Serialize the current node and recursively serialize left and right subtrees
return str(node.val) + "," + helper(node.left) + helper(node.right)
# Start serialization from the root
return helper(root)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
# Convert the string data back into a list of node values
data_list = data.split(',')
# Helper function to recursively build the tree from the data list
def helper():
if not data_list:
return None
# Get the next value in the list
val = data_list.pop(0)
if val == "#":
return None # '#' indicates a null node
# Create a new TreeNode for the current value
node = TreeNode(int(val))
# Recursively build the left and right subtrees
node.left = helper()
node.right = helper()
return node
# Start deserialization process
return helper()Explanation:
- TreeNode Definition:
- A
TreeNodeis a simple class with a value (val), and pointers to the left and right children (left,right).
- A
- Serialization (
serializemethod):- We define a helper function
helper(node)that performs a pre-order traversal of the binary tree. - When encountering a non-null node, we append the node’s value followed by a comma.
- If the node is
None(i.e., it doesn’t exist), we append"#,"to represent the null node. - The serialized string for the entire tree is generated by recursively visiting all nodes and appending their values or
#symbols forNonenodes.
- We define a helper function
- Deserialization (
deserializemethod):- We first split the serialized string by commas to get a list of node values.
- The helper function
helper()recursively builds the tree:- For each value, if it is
"#", we returnNone(indicating a null node). - If it is a valid number, we create a new
TreeNode, and recursively set its left and right children by callinghelper()on the remaining part of the list.
- For each value, if it is
- The tree is reconstructed in the same order it was serialized.
Solution in C++
C++
#include <string>
#include <sstream>
#include <queue>
using namespace std;
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
// Helper function to perform pre-order traversal
string result;
serializeHelper(root, result);
return result;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
// Split the data string into tokens (node values)
queue<string> nodes;
stringstream ss(data);
string token;
while (getline(ss, token, ',')) {
nodes.push(token);
}
// Rebuild the tree using the tokenized data
return deserializeHelper(nodes);
}
private:
// Helper function to serialize the tree
void serializeHelper(TreeNode* node, string& result) {
if (node == nullptr) {
result += "#,"; // Mark null nodes with '#'
return;
}
result += to_string(node->val) + ","; // Serialize the current node value
// Recursively serialize the left and right subtrees
serializeHelper(node->left, result);
serializeHelper(node->right, result);
}
// Helper function to deserialize the string into a tree
TreeNode* deserializeHelper(queue<string>& nodes) {
// If the queue is empty, return nullptr
if (nodes.empty()) return nullptr;
// Get the next value from the queue
string val = nodes.front();
nodes.pop();
// If the value is "#", it represents a null node
if (val == "#") return nullptr;
// Otherwise, create a new TreeNode with the integer value
TreeNode* node = new TreeNode(stoi(val));
// Recursively build the left and right subtrees
node->left = deserializeHelper(nodes);
node->right = deserializeHelper(nodes);
return node;
}
};Solution in Javascript
JavaScript
var serialize = function(root) {
// Helper function to perform pre-order traversal
function helper(node) {
if (node === null) {
return "#"; // Use '#' to represent a null node
}
// Serialize the current node and recursively serialize left and right subtrees
return node.val + "," + helper(node.left) + "," + helper(node.right);
}
// Start serialization from the root
return helper(root);
};
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function(data) {
// Split the data string into an array of node values
const nodes = data.split(",");
// Helper function to recursively build the tree from the array
function helper() {
// If there are no more nodes to process, return null
if (nodes.length === 0) return null;
// Get the first value from the array
const val = nodes.shift();
// If the value is '#', it indicates a null node
if (val === "#") return null;
// Create a new TreeNode for the current value
const node = new TreeNode(parseInt(val));
// Recursively build the left and right subtrees
node.left = helper();
node.right = helper();
return node;
}
// Start deserialization process
return helper();
};Solution in Java
Java
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
// Use a StringBuilder to efficiently build the string
StringBuilder result = new StringBuilder();
serializeHelper(root, result);
return result.toString(); // Convert StringBuilder to String
}
// Helper function for serialization
private void serializeHelper(TreeNode node, StringBuilder result) {
if (node == null) {
result.append("#,"); // Use '#' to denote null nodes
return;
}
result.append(node.val).append(","); // Append the current node's value
serializeHelper(node.left, result); // Recursively serialize the left subtree
serializeHelper(node.right, result); // Recursively serialize the right subtree
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
// Split the string by commas to get individual node values
String[] nodes = data.split(",");
// Use an index array to keep track of our position in the nodes array
return deserializeHelper(nodes, new int[1]);
}
// Helper function for deserialization
private TreeNode deserializeHelper(String[] nodes, int[] index) {
// If the current index points to a null marker, return null
if (index[0] >= nodes.length || nodes[index[0]].equals("#")) {
index[0]++; // Move to the next index
return null;
}
// Create a new TreeNode with the current value
TreeNode node = new TreeNode(Integer.parseInt(nodes[index[0]]));
index[0]++; // Move to the next index
// Recursively build the left and right subtrees
node.left = deserializeHelper(nodes, index);
node.right = deserializeHelper(nodes, index);
return node; // Return the constructed TreeNode
}
}