题解 | #序列化二叉树#
序列化二叉树
http://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84
时间损耗方面，超过99%的python提交代码 主要使用层次遍历的方式，空节点采用值为-1的节点代替，若一层节点的值均为-1则认为该层不存在。构造树采用了递归的方法，除了判断该节点是否在列表中存在外，通过判断节点的值是否为-1决定是否继续递归构造其子树。
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
