本文共 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])
转载地址：http://dcwbf.baihongyu.com/