Serialize and Deserialize Binary Tree

LeetCode 297 • Hard • Trees

Preorder DFS: visit node, left, right. Use "N" for null. Tree [1,2,3,null,null,4,5] → "1,2,N,N,3,4,N,N,5,N,N"

TimeO(n)

SpaceO(n)

node: — out: —

Current

Visited

node—

out—

Speed:

Ready

Press Play. Preorder DFS: visit node, left, right. Append val or "N" for null. Comma-separated.

Whiteboard

Size:3

Type It

Practice until you don't need to look. Preorder: visit node, left, right. Use "N" for null.

═══ SERIALIZE & DESERIALIZE — PREORDER ═══

PATTERN ▸ Preorder DFS + "N" for null O(n) · O(n)

① SERIALIZE

def serialize(node): if not node: return "N"

return str(node.val) + "," + serialize(left) + "," + serialize(right)

② DESERIALIZE

vals = data.split(","); i = 0

def build(): nonlocal i; if vals[i]=="N": i+=1; return None

node = TreeNode(int(vals[i])); i+=1

node.left = build(); node.right = build(); return node

your implementation

Verify: