1、序列化：层次遍历【用字符串来存储】
2、反序列化：用队列存已经建立的节点，从序列化后的字符串列表取数来建立树
def serialize(self, root): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ if not root: return "" prev,strres=[root],"" while prev: cur=[] while prev: node=prev.pop(0) if node: strres+=str(node.val)+',' cur.append(node.left) cur.append(node.right) else: strres+='#'+',' prev=cur return strres[:-1] def deserialize(self, data): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ if not data: return None listdata=data.split(',') root=TreeNode(listdata[0]) queue=[root] i=0 while queue: node=queue.pop(0) if listdata[i+1]!='#': node.left=TreeNode(listdata[i+1]) queue.append(node.left) i+=1 if listdata[i+1]!='#': node.right=TreeNode(listdata[i+1]) queue.append(node.right) i+=1 return root 二、前序遍历的序列化：
代码：
class Tree: def __init__(self,val): self.val =val self.left = None self.right = None#主要函数def preOrder(head): if not head: return '#!' s = str(head.val) + '!' s += preOrder(head.left) s += preOrder(head.right) return stree = Tree(12)tree.left = Tree(3)preOrder(tree)
反序列化：
class Tree: def __init__(self,val): self.val =val self.left = None self.right = Nonedef repreOrder(s): if not s: return None arr = s.split('!') return reconPre(arr)def reconPre(arr): if arr: value = arr.pop(0) if value == '#': return None head = Tree(int(value)) head.left = reconPre(arr) head.right = reconPre(arr) return head else: return Nones = '12!3!#!#!#!'repreOrder(s)
3、前序遍历和中序遍历反序列化
def buildTree(self, preorder, inorder): if preorder and inorder: root=TreeNode(preorder[0]) k=inorder.index(preorder[0]) m=len(inorder[:k]) root.left=self.buildTree(preorder[1:1+m],inorder[0:k]) root.right=self.buildTree(preorder[1+m:],inorder[k+1:]) return root