给定一个二叉树的完整的层次遍历序列(包含所有节点,包括空节点),利用这个序列生成一颗二叉树。
我们首先来看怎样对一颗二叉树进行层序遍历,下图所示的二叉树层次遍历的结果为[a,b,c,d,e],在这个过程中,我们首先保存根节点a,然后遍历a的左右节点b,d并保存下来,然后遍历b的左右子节点并保存,然后遍历d的子节点并保存,直到完成了整棵树的遍历。所以这个过程是一个保存节点然后取出遍历的过程,它符合先进先出的顺序,所以才用队列来实现
首先定义二叉树的类:
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
层序遍历:
def PrintFromTopToBottom(root):
ans=[]
if root==None:
return ans
else:
q=[root]
while q:
node=q.pop(0)
ans.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return ans
利用层序生成二叉树则是一个相反的过程,对于序列[a,b,c,d,None,None,e]来说,b c是a的子节点,d None是b的子节点,None e是c的子节点。如果序列为l,那么l[0]是根节点,l[1]和l[2]是l[0]左右子结点,l[3]和l[4]是l[1]左右子节点......,所以每次取出两个节点,依次作为之前节点的子节点。代码如下:
def createtree(l):
if l[0]:
root=TreeNode(l[0])
nodes=[root]
id=1
while nodes and id<len(l):
node=nodes[0]#依次为每个节点分配子节点
node.left=TreeNode(l[id]) if l[id] else None
nodes.append(node.left)
node.right=TreeNode(l[id+1]) if id<len(l)-1 and l[id+1] else None
nodes.append(node.right)
id+=2#每次取出两个节点
nodes.pop(0)
return root
else:
return None
python版本:3.6