本文共 6203 字，大约阅读时间需要 20 分钟。

给定二叉树T（树深度不超过H<=10，深度从1开始，节点个数N<1024，节点编号1~N）的层序和中序遍历，输出T从左向右叶子节点以及树先序和后序遍历序列

输入两行，分别代表层序和中序遍历结果，节点编号按单个空格分开

依次输出  从左向右叶子节点 ，先序， 后序 遍历 。 节点编号按空格分开

例如：输入

3 5 4 2 6 7 1

2 5 3 6 4 7 1

输出

2 6 1

3 5 2 4 6 7 1

2 5 6 1 7 4 3

class TreeNode(object):    def __init__(self, x):        self.left = None        self.right = None        self.val = xclass Solution(object):    def __init__(self):        self.leaf = []    def creatTree(self, bfsorder, inorder):        """        从中序遍历找出左右子树，然后再从序列层次遍历中找出左右子树序列，重建二叉树        :param bfsorder:        :param inorder:        :return:        """        if len(bfsorder) < 1:            return        if len(bfsorder) == 1 and bfsorder[0] not in self.leaf:            self.leaf.append(bfsorder[0])            # print(self.leaf)        root = TreeNode(bfsorder[0])        root_index = inorder.index(root.val)  # 根节点在中序遍历的索引        left_in = inorder[:root_index]  # 中序遍历的左子树        right_in = inorder[root_index + 1:]  # 中序遍历的右子树        left_bsf = [x for x in bfsorder if x in left_in]  # 层次遍历的左子树、        right_bfs = [x for x in bfsorder if x in right_in]        root.left = self.creatTree(left_bsf, left_in)        root.right = self.creatTree(right_bfs, right_in)        return root    def preorder(self, root):  # 前序递归        if not root:            return []        return [root.val] + self.preorder(root.left) + self.preorder(root.right)        def preorder_for(self,root):  # 前序循环：前左右        if not root:            return []        stack = [root]        result=[]        while len(stack)>0:            result.append(root.val)            if root.right is not None:                stack.append(root.right)            if root.left is not None:                stack.append(root.left)            root=stack.pop()        return result                def inorder(self,root):  # 中序递归        if root is None:            return []        return self.inorder(root.left)+[root.val]+self.inorder(root.right)        def inorder_for(self,root):  # 中序循环：左前右        if not root:            return []        stack=[]        pos = root        result=[]        while len(stack)>0 or pos:            if pos:                stack.append(pos)                pos=pos.left            else:                pos=stack.pop()                result.append(pos.val)                pos=pos.right        return result            def postorder(self, root):  # 后序递归        if not root:            return []        return self.postorder(root.left) + self.postorder(root.right) + [root.val]        def postorder_for(self, root):  # 后序循环：左右前        # 使用两个栈结构        # 第一个栈进栈顺序：左节点->右节点->跟节点        # 第一个栈弹出顺序： 跟节点->右节点->左节点(先序遍历栈弹出顺序：跟->左->右)        # 第二个栈存储为第一个栈的每个弹出依次进栈        # 最后第二个栈依次出栈        if not root:            return []        stack1=[root]        stack2=[]        result=[]        while len(stack1)>0:            root = stack1.pop()            stack2.append(root)            if root.left:                stack1.append(root.left)            if root.right:                stack1.append(root.right)        while len(stack2)>0:            result.append(stack.pop())        return result        def levelorder(self, node, level):  # 层序循环/宽度优先遍历            if not node:                return []            else:                sol[level-1].append(node.val)                if len(sol) == level:  # 遍历到新层时，只有最左边的结点使得等式成立                    sol.append([])                    print(sol,level)                self.levelorder(node.left, level+1)                self.levelorder(node.right, level+1)    def levelorder_for(self,root):  # 采用循环方式:从上到下、从左到右按层遍历        # 先进先出选用队列结构queue        if root is None:            return []        queue=[root]        result = []        while len(queue)>0:            root = queue.pop(0)            result.append(root.val)            if root.left:                queue.append(root.left)            if root.right:                queue.append(root.right)        return result        def treenodenums(self,root):  # 二叉树的节点个数        pass        def treedeep(self,root):  #求二叉树的深度，使用递归的方式        if not root:            return 0        left = self.treedeep(root.left)        right = self.treedeep(root.right)        if left>=right:            return left+1        else:            return right+1    def treedeep_for(self,root):  # 非递归，使用层次遍历方式        if not root:            return 0        queue=[root]        result = [] # 层序遍历结果        tmp = [] # 存储同层节点        count = 0        while len(queue)>0:            n=len(queue) # 一层的节点数量            tmp=[] # 每一层清空            for i in range(n): # 将本层的节点数量全部释放，同时保存下一层的所有节点                root = queue.pop(0)                tmp.append(root.val)                if root.left:                    queue.append(root.left)                if root.right:                    queue.append(root.right)            if len(tmp)>0:                result+=tmp  # 将这一层的遍历结果放进result                count +=1  # 并且层数加1        return count    def is_balancetree(self,root):  # 判断给定的二叉树是不是一棵平衡树（左右子树的深度差不超过1）        if not root:     # 对每一个节点判断其左右子树的深度，从上到下；不足点就是子节点需要被遍历多次            return True        if abs(self.treedeep(root.left)-self.treedeep(root.right))>1:            return False        return is_balancetree(root.left) and is_balancetree(root.right)    def is_balancetree_for(self,root):  # 使用后序遍历的方式，左右中，最后才遍历根节点，因此只需要遍历一次。        if not root:            return True        def dif(p):  # 后序遍历            if not p:                return 0            left = dif(p.left)            if left==-1:                return -1            right = dif(p.right)            if right ==-1:                return -1            if abs(left-right)>1:  # 如果左右子树深度差大于1，那么就为-1                return -1            return max(left,right)+1  # 否则记录深度，从下往上，层级依次加1        return dif(root)!=-1                                         s = Solution()bfsorder = [int(x) for x in input().split()]inorder = [int(x) for x in input().split()]root = s.creatTree(bfsorder, inorder)  pre = s.preorder(root)inorder = s.inorder(root)post = s.postorder(root)sol = [[]]s.levelorder(root,1)print('叶子节点',' '.join(list(map(str,s.leaf))))print('前序',' '.join(list(map(str,pre))))print('中序',' '.join(list(map(str,inorder))))print('后序',' '.join(list(map(str,post))))print('层序',sol[:-1])

转载地址：https://blog.csdn.net/zz2230633069/article/details/102519702 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！