Core Insight Ask each subtree for exactly the information its parent needs, then combine the two answers.
Common Pitfall Define the base case before combining left and right subtree results.
Description
Design serialize/deserialize methods for a binary tree.
Constraints
- Time Complexity:
O(n) - Space Complexity:
O(n)
Tags
stringtreedfsbfsdesign
Implementation Plan Translate the invariant into these small, testable moves.
- Define what one recursive call returns.
- Handle an empty node.
- Recurse into children.
- Combine the child results at the current node.
class Codec:
def serialize(self, root):
res = []
def dfs(node):
if not node:
res.append("N")
return
res.append(str(node.val))
dfs(node.left)
dfs(node.right)
dfs(root)
return ",".join(res)
def deserialize(self, data):
vals = data.split(",")
self.i = 0
def dfs():
if vals[self.i] == "N":
self.i += 1
return None
node = TreeNode(int(vals[self.i]))
self.i += 1
node.left = dfs()
node.right = dfs()
return node
return dfs()