Serialize and Deserialize Binary Tree
Implement a serializer and deserializer for a binary tree. Use preorder tokens with # for every null child. Reconstruct the tree from that string.
Work through the cases
3 examplesInput notation
A binary tree in level order on one line, using null for missing children. Omit trailing nulls; use null for an empty tree.Expected result
Preorder serialization on line 1; reconstructed level order on line 2, omitting trailing nulls.Case 1
Input
1 2 3
Expected output
1 2 # # 3 # # 1 2 3
Case 2
Input
null
Expected output
# null
Case 3
Input
-1 null 2
Expected output
-1 # 2 # # -1 null 2
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
A general binary tree must record missing children; storing only present values loses shape. Level order writes \# for nulls so parent–child slots can be rebuilt. Serialize by enqueueing both children; deserialize assigns the next two tokens as the front node’s left and right.
We can use level order traversal to serialize the binary tree. Starting from the root node, we add the nodes of the binary tree to the queue in the order from top to bottom, from left to right. Then we dequeue the nodes in the queue one by one. If the node is not null, we add its value to the serialized string; otherwise, we add a special character #. Finally, we return the serialized string.
During deserialization, we split the serialized string by the delimiter to get a string array, and then add the elements in the string array to the queue in order. The elements in the queue are the nodes of the binary tree. We dequeue the elements from the queue one by one. If the element is not #, we convert it to an integer and use it as the value of the node, and then add the node to the queue; otherwise, we set it to null. Finally, we return the root node.
The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the binary tree.
/**
* 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) {
if (root == null) {
return null;
}
List<String> ans = new ArrayList<>();
Deque<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode node = q.poll();
if (node != null) {
ans.add(node.val + "");
q.offer(node.left);
q.offer(node.right);
} else {
ans.add("#");
}
}
return String.join(",", ans);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null) {
return null;
}
String[] vals = data.split(",");
int i = 0;
TreeNode root = new TreeNode(Integer.valueOf(vals[i++]));
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode node = q.poll();
if (!"#".equals(vals[i])) {
node.left = new TreeNode(Integer.valueOf(vals[i]));
q.offer(node.left);
}
++i;
if (!"#".equals(vals[i])) {
node.right = new TreeNode(Integer.valueOf(vals[i]));
q.offer(node.right);
}
++i;
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.