Serialize and Deserialize Binary Tree

2 min read
LC-Hard
Binary Tree

Oct 21, 2022

3 years ago

LeetCode

jjj

Optimal Solution

Pre-order Traversal
The deserialization is just another DFS, where each call you increment i, which is the index of your tokens
Draw it out on paper, and you'll understand
We keep the variable i outside of the function because we also need to increment it for null nodes- these don't include a subsequent call to our DFS function, and we need to somehow update it for the next node that we're assigning

Time	Space	Explanation
`O()`	`O()`

def serialize(self, root): nodes = [] def dfs(node): if node is None: nodes.append('N') return nodes.append(str(node.val)) dfs(node.left) dfs(node.right) dfs(root) return ' '.join(nodes) def deserialize(self, data): tokens = data.split() i = 0 def dfs(): nonlocal i if tokens[i] == 'N': i += 1 return None node = TreeNode(int(tokens[i])) i += 1 node.left = dfs() node.right = dfs() return node return dfs()

Less Optimal Solution

Using Breadth-first Search AKA Level Order Traversal
This solution is correct but TLEs on LeetCode because of a very unbalanced tree (basically just right nodes all along)
I'm happy that I came up with the solution on my own, but damn i'm sad it does not work.

def serialize(self, root): nodes = [] q = deque([root]) while q: nodes_left = False for _ in range(len(q)): node = q.popleft() if node == 'N': nodes.append('N') q.append('N') q.append('N') elif node: nodes_left = True nodes.append(str(node.val)) q.append(node.left if node.left else 'N') q.append(node.right if node.right else 'N') if not nodes_left: break return '/'.join(nodes) def deserialize(self, data): if data == '': return None tokens = ['~'] + data.split('/') def assign(i): if i >= len(tokens): return None val = tokens[i] if val == 'N': return None root = TreeNode(val) root.left = assign(2 * i) root.right = assign(2 * i + 1) return root return assign(1)