Preorder DFS
Intuition
We can serialize the tree using a preorder traversal (node, left, right), recording each node's value and using a sentinel like "null" for empty children. This captures the complete structure because knowing where null children are lets us unambiguously reconstruct the tree. During deserialization, we consume tokens one by one in the same preorder sequence: each token either creates a node (and we recursively build its left and right subtrees) or signals a null child.
Algorithm
- **Serialize:** Perform a preorder traversal. For each node, append its value to the result string. For null nodes, append "null". Separate tokens with commas.
- **Deserialize:** Split the string by commas into a list of tokens. Use a pointer or iterator to track the current position.
- If the current token is "null", advance the pointer and return null.
- Otherwise, create a new node with the token's integer value, advance the pointer, and recursively build the left and right subtrees.
Time
O(n) for both serialize and deserializeSpaceO(n)Code (C++ · Java · Python · Go)
class Codec {
public:
string serialize(TreeNode* root) {
if (root == nullptr) return "null";
return to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);
}
TreeNode* deserialize(string data) {
istringstream ss(data);
return buildTree(ss);
}
private:
TreeNode* buildTree(istringstream& ss) {
string token;
getline(ss, token, ',');
if (token == "null") return nullptr;
TreeNode* node = new TreeNode(stoi(token));
node->left = buildTree(ss);
node->right = buildTree(ss);
return node;
}
};public class Codec {
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serializeHelper(root, sb);
return sb.toString();
}
private void serializeHelper(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append("null,");
return;
}
sb.append(node.val).append(",");
serializeHelper(node.left, sb);
serializeHelper(node.right, sb);
}
public TreeNode deserialize(String data) {
Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));
return buildTree(queue);
}
private TreeNode buildTree(Queue<String> queue) {
String val = queue.poll();
if (val.equals("null")) return null;
TreeNode node = new TreeNode(Integer.parseInt(val));
node.left = buildTree(queue);
node.right = buildTree(queue);
return node;
}
}def serialize(root: Optional[TreeNode]) -> str:
result = []
def dfs(node):
if not node:
result.append("null")
return
result.append(str(node.val))
dfs(node.left)
dfs(node.right)
dfs(root)
return ",".join(result)
def deserialize(data: str) -> Optional[TreeNode]:
tokens = iter(data.split(","))
def build():
val = next(tokens)
if val == "null":
return None
node = TreeNode(int(val))
node.left = build()
node.right = build()
return node
return build()import (
"strconv"
"strings"
)
type Codec struct{}
func Constructor() Codec {
return Codec{}
}
func (c *Codec) serialize(root *TreeNode) string {
var result []string
var dfs func(*TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
result = append(result, "null")
return
}
result = append(result, strconv.Itoa(node.Val))
dfs(node.Left)
dfs(node.Right)
}
dfs(root)
return strings.Join(result, ",")
}
func (c *Codec) deserialize(data string) *TreeNode {
tokens := strings.Split(data, ",")
idx := 0
var build func() *TreeNode
build = func() *TreeNode {
if idx >= len(tokens) || tokens[idx] == "null" {
idx++
return nil
}
val, _ := strconv.Atoi(tokens[idx])
idx++
node := &TreeNode{Val: val}
node.Left = build()
node.Right = build()
return node
}
return build()
}