#297
Serialize and Deserialize Binary Tree
Hard Preorder with null markers
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Design an encoder that turns a binary tree into a string and a decoder that rebuilds the exact same tree from it.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: turn a tree into a string and back.
Why this works: preorder with "#" for null fully describes the shape; reading tokens back in the same order rebuilds it.
Example: 1 (2, 3 (4, 5))
"1,2,#,#,3,4,#,#,5,#,#"✦Hints open one at a time
Preorder alone is ambiguous, but preorder with explicit null markers is not.
Write values separated by commas and "#" for null.
Rebuild with recursion that reads tokens in the same order.
↗Approach
serialize: preorder, append value or "#". deserialize: split into tokens, keep a pointer; build(): read a token, "#" → null, else create a node and build its left then right.
</>Solution (Java)
import java.util.*;
/**
* class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; } } // provided by LeetCode
*/
public class Codec {
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
write(root, sb);
return sb.toString();
}
private void write(TreeNode n, StringBuilder sb) {
if (n == null) {
sb.append("#,"); // null marker keeps the shape
return;
}
sb.append(n.val).append(',');
write(n.left, sb);
write(n.right, sb);
}
public TreeNode deserialize(String data) {
Deque<String> tokens = new ArrayDeque<>(Arrays.asList(data.split(",")));
return read(tokens);
}
private TreeNode read(Deque<String> tokens) {
String t = tokens.poll();
if (t.equals("#")) return null;
TreeNode n = new TreeNode(Integer.parseInt(t));
n.left = read(tokens);
n.right = read(tokens);
return n;
}
}!Common mistake
Forgetting the null markers, so different trees produce the same string.
Complexity
- Time: O(n) both ways.
- Space: O(n).
Topic: Binary Trees
🎬 Episodes 53–60: video coming soon