层序遍历二叉树完整层序重建二叉树 python

　　给定一个二叉树的完整的层次遍历序列（包含所有节点，包括空节点），利用这个序列生成一颗二叉树。

　　我们首先来看怎样对一颗二叉树进行层序遍历，下图所示的二叉树层次遍历的结果为[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

巴特西

层序遍历二叉树完整层序重建二叉树 python

最新文章

热门文章

巴特西

层序遍历二叉树 完整层序重建二叉树 python

最新文章

热门文章

层序遍历二叉树完整层序重建二叉树 python