Design an algorithm to serialize a binary tree to a string and deserialize the string back to the tree. No constraints on format.
Input: root=[1,2,3,null,null,4,5] → serialize → "1,2,N,N,3,4,N,N,5,N,N" → deserialize → same tree
Use preorder DFS. During serialization, output val for each node and "N" for nulls. During deserialization, split by comma and reconstruct using a queue.
- Serialize: preorder DFS, append node.val or "N", separate by comma.
- Deserialize: split string by comma into queue.
- Recursive build: poll from queue; if "N" return null; else create node, recurse left, recurse right.
import java.util.*;
public class Codec {
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
dfs(root, sb);
return sb.toString();
}
private void dfs(TreeNode node, StringBuilder sb) {
if (node == null) { sb.append("N,"); return; }
sb.append(node.val).append(",");
dfs(node.left, sb); dfs(node.right, sb);
}
public TreeNode deserialize(String data) {
Deque<String> q = new ArrayDeque<>(Arrays.asList(data.split(",")));
return build(q);
}
private TreeNode build(Deque<String> q) {
String val = q.poll();
if (val.equals("N")) return null;
TreeNode node = new TreeNode(Integer.parseInt(val));
node.left = build(q); node.right = build(q);
return node;
}
}
- Time Complexity: O(N)
- Space Complexity: O(N)