動機
原來 中序加前序去重建tree是有限制的,val不能重複!!
Problem
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Example 1:
Input: root = [1,2,3,null,null,4,5]Output: [1,2,3,null,null,4,5]
Example 2:
Input: root = []Output: []
Example 3:
Input: root = [1]Output: [1]
Example 4:
Input: root = [1,2]Output: [1,2]
Constraints:
- The number of nodes in the tree is in the range
[0, 104]
. -1000 <= Node.val <= 1000
Sol: dfs
不論哪一種走訪,都是看序列化時怎麼走,反序列化就照著走
class Codec:
def inorder(self,r):
if not r:
self.ino.append('x')
else:
self.ino.append(str(r.val))
self.inorder(r.left)
self.inorder(r.right)
def serialize(self, root):
if not root:
return ""
else:
self.ino = []
self.inorder(root)
#print(self.ino)
return ','.join(self.ino)
def dfs(self):
self.i += 1
if self.data[self.i] != 'x':
root = TreeNode()
root.val = int(self.data[self.i])
root.left = self.dfs()
root.right = self.dfs()
return root
else:
return None
def deserialize(self, data):
if not data:
return None
self.data = data.split(',')
self.i = -1
return self.dfs()
Sol: bfs
class Codec:
def serialize(self, root):
if not root:
return ""
else:
ret = []
q = deque([root])
while q:
tmp = q.popleft()
if tmp:
ret.append(str(tmp.val))
q.append(tmp.left)
q.append(tmp.right)
else:
ret.append('x')
return ','.join(ret)
def deserialize(self, data):
if not data:
return None
else:
data = data.split(',')
ret = TreeNode()
ret.val = int(data[0])
q = deque([ret])
i = 1
while q and i < len(data):
root = q.popleft()
now = data[i] if i < len(data) else 'x'
if now != 'x':
root.left = TreeNode()
root.left.val = int(now)
q.append(root.left)
i += 1
now = data[i] if i < len(data) else 'x'
if now != 'x':
root.right = TreeNode()
root.right.val = int(now)
q.append(root.right)
i += 1
return ret