# 题解 | #序列化二叉树#

http://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84

``````from typing import List

class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

class Solution:
def Serialize(self, root):
# write code here
if not root:
return None
resstr = []
nodeduilie = [root]
deep = 1
while True:
count = 2 ** (deep - 1)
# 利用值为-1的节点标记空的位置
# flag 用来标记一层至少有一个节点，不然就终止
flag = 0
for i in range(count):
tempnode = nodeduilie.pop(0)
resstr.append(tempnode.val)
if tempnode.left and tempnode.left.val != -1:
nodeduilie.append(tempnode.left)
flag = 1
else:
nodeduilie.append(TreeNode(-1))
if tempnode.right and tempnode.right.val != -1:
nodeduilie.append(tempnode.right)
flag = 1
else:
nodeduilie.append(TreeNode(-1))
# flag标志着下一层，是否有真实的节点
if flag == 0:
break
# 标志下次循环的是第几层的节点，用于计算一层的节点数
deep += 1
return resstr

def Deserialize(self, s):
# write code here
if not s:
return None
root = TreeNode(s[0])

return self.buildtree(root, s, 0)

def buildtree(self, root: TreeNode, alist: List[int], n):
# 根节点是列表中的第n个，它的左孩子则是第2n + 1个，右孩子为第2n+2个
if 2 * n + 1 > len(alist) - 1:
return root
if alist[2 * n + 1] != -1:
root.left = TreeNode(alist[2 * n + 1])
root.left = self.buildtree(root.left, alist, 2 * n + 1)
else:
root.left = None
if 2 * n + 2 > len(alist) - 1:
return root
if alist[2 * n + 2] != -1:
root.right = TreeNode(alist[2 * n + 2])
root.right = self.buildtree(root.right, alist, 2 * n + 2)
else:
root.right = None

return root
``````

04-18 17:37

3 收藏 评论