二叉树的问题汇总
发布日期:2021-06-29 11:42:04
浏览次数:3
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月04日 04时31分07秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
华为被超越!这家公司成中国最大智能手机制造商,不是小米!
2019-04-29
芯片为什么持续缺货?
2019-04-29
美国无人机在火星首飞成功,创造历史,3米飞行高度悬停30秒
2019-04-29
缺货涨价很久的MCU的国产和国外厂家汇总!(80家)
2019-04-29
华为重磅反击,鸿蒙来了!
2019-04-29
常用电子接口大全,遇到不认识的,就翻出来对照辨认!
2019-04-29
芯片IC附近为啥要放0.1uF的电容?
2019-04-29
电赛 | 19年全国一等奖,北航学子回忆录。
2019-04-29
电赛 | 19年全国一等奖,北航学子回忆录(上)
2019-04-29
电赛 | 19年全国一等奖,北航学子回忆录(下)
2019-04-29
突破!台积电1nm芯片,有了新进展。
2019-04-29
一文读懂全系列树莓派!
2019-04-29
自制一个害羞的口罩,见人就闭嘴,戴着可以喝奶茶
2019-04-29
聊聊我是如何编程入门的
2019-04-29
J-Link该如何升级固件?
2019-04-29
485通信自动收发电路,历史上最详细的解释
2019-04-29
一位头发发白的神人教你怎么写程序,运维,买电脑,写文章,平面设计!
2019-04-29
「第三篇」全国电子设计竞赛,这些你必须知道的比赛细节,文末附上近十年电赛题目下载...
2019-04-29
5G小科普(漫画版,So easy!)
2019-04-29
「第四篇」电赛控制题可以准备一些什么?
2019-04-29