尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
二叉树练习
中序遍历classTreeNode(object):def__init__(self,x):self.valx self.leftNoneself.rightNonedefin_order_traversal(root):# 中序res[]stack[]#借用栈ifrootisNone:returnres currootwhilelen(stack)!0orcurisnotNone:whilecurisnotNone:stack.append(cur)curcur.left nodestack.pop()res.append(node.val)curnode.rightreturnres# 中序打印二叉树递归definOrderTraverse(node):ifnodeisNone:returnNoneinOrderTraverse(node.left)print(node.val)inOrderTraverse(node.right)前序遍历classTreeNode(object):def__init__(self,x):self.valx self.leftNoneself.rightNonedefpre_order_traversal(root):# 前序result[]stack[]stack.append(root)whilelen(stack)!0:nodestack.pop()ifnodeisNone:continueresult.append(node.val)stack.append(node.right)stack.append(node.left)returnresult# 先序打印二叉树递归defpreOrderTraverse(node):ifnodeisNone:returnNoneprint(node.val)preOrderTraverse(node.left)preOrderTraverse(node.right)后序遍历classTreeNode(object):def__init__(self,x):self.valx self.leftNoneself.rightNonedefpost_order_traversal(root):# 后序 前序遍历为 root - left - right后序遍历为 left - right - root 可以修改前序遍历成为 root - right - left那么这个顺序就和后序遍历正好相反 result[]stack[]stack.append(root)whilelen(stack)!0:nodestack.pop()ifnodeisNone:continueresult.append(node.val)stack.append(node.left)stack.append(node.right)returnresult[::-1]# 后序打印二叉树递归defpostOrderTraverse(node):ifnodeisNone:returnNonepostOrderTraverse(node.left)postOrderTraverse(node.right)print(node.val)从上往下打印二叉树简单题目描述从上往下打印出二叉树的每个节点同层节点从左至右打印。思路根节点不存在 返回空开辟queue空间 初始化为[root] 队列意味着一层一层的遍历开辟放结果的数组 res当队列不为空时while计算这一层有几个节点n遍历这一层for如果这一层不存在节点 退出for循环否则 取出一个节点 添加到放结果的数组res将下一层的节点都添加到队列 即如果该节点左右节点存在添加到队列返回res运行时间26ms占用内存5860kclassTreeNode:def__init__(self,x):self.valx self.leftNoneself.rightNonedefconstruct_tree():rootTreeNode(8)root.leftTreeNode(6)root.rightTreeNode(10)root.left.leftTreeNode(5)root.left.rightTreeNode(7)root.right.leftTreeNode(9)root.right.rightTreeNode(11)root.left.right.leftTreeNode(12)root.left.right.rightTreeNode(13)returnrootclassSolution:# 返回从上到下每个节点值列表例[1,2,3]defPrintFromTopToBottom(self,root):# write code hereifnotroot:return[]queue[root]res[]whilequeue:nlen(queue)for_inrange(n):ifnotqueue:breaktempqueue.pop(0)res.append(temp.val)iftemp.left:queue.append(temp.left)iftemp.right:queue.append(temp.right)returnres sSolution()treeconstruct_tree()ress.PrintFromTopToBottom(tree)print(res)#return [8, 6, 10, 5, 7, 9, 11, 12, 13]按之字形打印二叉树题目描述请实现一个函数按照之字形打印二叉树即第一行按照从左到右的顺序打印第二层按照从右至左的顺序打印第三行按照从左到右的顺序打印其他行以此类推。思路同上一道题不同之处在于添加了标记偶数行的标记 jj 初始化为-1 每开始新一行的循环 j 就加一最后每一行遍历完后 判断这是奇数行还是偶数行偶数行的话反转这一行的数值。第二个不同之处在于开辟了放每一行数值的暂存数组temp因为偶数行的话必须反转后才能添加到结果数组res里面。运行时间27ms占用内存5728kclassSolution:defPrint(self,pRoot):# write code hereifnotpRoot:return[]res[]#放结果的数组queue[pRoot]j-1#标记偶数行whilequeue:j1nlen(queue)temp[]#放这一行的节点数值for_inrange(n):nodequeue.pop(0)temp.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)ifj%2:#当j表示这一行为偶数行 反转这一行temp.reverse()res.append(temp)#把这一行确定的节点数值放进结果数组里returnres sSolution()treeconstruct_tree()ress.Print(tree)print(res)把二叉树打印成多行题目描述从上到下按层打印二叉树同一层结点从左至右输出。每一层输出一行。运行时间25ms占用内存5632kclassSolution:# 返回二维列表[[1,2],[4,5]]defPrint(self,pRoot):# write code hereifnotpRoot:return[]queue[pRoot]res[]whilequeue:nlen(queue)temp[]for_inrange(n):nodequeue.pop(0)temp.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)res.append(temp)# print(res)returnres#return [[8], [6, 10], [5, 7, 9, 11]]对称的二叉树题目描述请实现一个函数用来判断一颗二叉树是不是对称的。注意如果一个二叉树同此二叉树的镜像是同样的定义其为对称的。思路如果根节点不存在 返回真把每一层放进队列 queue [pRoot]当队列里有节点时 进行以下操作看这一层有多少个节点 n如果非根节点且这一层节点数是奇数则返回false否则重点判断这一行最左和最右是否一样【判断两个节点一样么两节点都不存在则两节点一样两节点都存在且数值一样则两节点一样否则返回不一样】遍历这一行弹出队列中的一个节点如果该节点不存在 过否则将下一层的节点都添加到队列 即如果该节点左右节点存在添加到队列运行时间25ms占用内存5732kclassSolution:defisEqual(self,p1,p2):ifnotp1andnotp2:returnTrueelifp1andp2andp1.valp2.val:returnTrueelse:returnFalsedefisSymmetrical(self,pRoot):# write code hereifnotpRoot:returnTruequeue[pRoot]whilequeue:# print(queue)nlen(queue)ifqueue[0]!pRootandn%2!0:returnFalseforiinrange(n//2):ifnotself.isEqual(queue[i],queue[-1-i]):returnFalsefor_inrange(n):nodequeue.pop(0)ifnotnode:continuequeue.append(node.left)queue.append(node.right)returnTrue二叉树的下一个结点题目描述给定一个二叉树和其中的一个结点请找出中序遍历顺序的下一个结点并且返回。注意树中的结点不仅包含左右子结点同时包含指向父结点的指针。思路分情况讨论第一节点p的右节点存在p的下一个节点 则为p的右子树的最左节点 [1.1】第二节点p的右节点不存在的话 分两种情况第一 节点p的右节点不存在的话 且 p为其父节点的左子节点p的下一个节点 则为p的父节点 【2.1】第二节点p的右节点不存在的话 且 p为其父节点的右子节点 p的下一个节点 为 沿着父节点往上遍历 找到一个点 满足该点是其父节点的左子节点。若该点不存在则p的下一个节点不存在【2.2】如果该节点为空 返回Nonep的右节点存在的话找到右子树的最左节点 返回节点p的右节点不存在的话 且 p为其父节点的右子节点 时关键往上遍历 当pNode是自己父节点的左子节点时跳出while返回pNode的父节点运行时间26ms占用内存5864kdefconstruct_tree():rootTreeNode(1)root.leftTreeNode(2)root.rightTreeNode(3)root.left.leftTreeNode(4)root.left.rightTreeNode(5)root.right.leftTreeNode(6)root.right.rightTreeNode(7)root.left.right.leftTreeNode(8)root.left.right.rightTreeNode(9) root TreeNode(a) root.left TreeNode(b) root.right TreeNode(c) root.left.left TreeNode(d) root.left.right TreeNode(e) root.right.left TreeNode(f) root.right.right TreeNode(g) root.left.right.left TreeNode(h) root.left.right.right TreeNode(i) root.parentNoneroot.left.parentroot root.right.parentroot root.left.left.parentroot.left root.left.right.parentroot.left root.right.left.parentroot.right root.right.right.parentroot.right root.left.right.left.parentroot.left.right root.left.right.right.parentroot.left.rightreturnrootclassTreeNode:def__init__(self,x):self.valx self.leftNoneself.rightNoneself.parentNoneclassSolution:defGetNext(self,pNode):# write code hereifnotpNode:returnNoneifpNode.right:#ppNode.rightwhilep.left:pp.leftreturnp#whilepNode.parentandpNode.parent.rightpNode:pNodepNode.parentreturnpNode.parent rootconstruct_tree()sSolution()#ress.GetNext(root.left.left)ress.GetNext(root.right.left)print(res.val)二叉树的深度题目描述输入一棵二叉树求该树的深度。从根结点到叶结点依次经过的结点含根、叶结点形成树的一条路径最长路径的长度为树的深度。思路队列queue 用来放每一层节点运行时间28ms占用内存5728kclassSolution:defTreeDepth(self,pRoot):# write code hereifnotpRoot:return0#根节点不存在 返回0queue[pRoot]# 把每一层放进队列deep0#深度初始化为0whilequeue:#当这一层有节点时nlen(queue)#看着一层有几个节点nfor_inrange(n):#遍历这一层的n个节点nodequeue.pop(0)#弹出一个并把弹出的节点的下一层的节点即左右子节点添加到队列ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)deep1#每一层遍历完 深度加一returndeep二叉搜索树的第k个结点题目描述给定一棵二叉搜索树请找出其中的第k小的结点。例如 5372468 中按结点数值大小顺序第三小结点的值为4。运行时间26ms占用内存5864k树的子结构题目描述输入两棵二叉树AB判断B是不是A的子结构。ps我们约定空树不是任意一个树的子结构重建二叉树中等题目描述输入某二叉树的前序遍历和中序遍历的结果请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}则重建二叉树并返回。思路用前序遍历找到根结点用根结点在中序遍历中切开左右子树递归重建二叉树前序数组为空时返回空用前序遍历找到根结点初始化一个为根值的树节点遍历后序数组找到根数值的索引位置i切分左右子树,递归调用本函数返回根节点运行时间42ms占用内存5724k# class TreeNode:# def __init__(self, x):# self.val x# self.left None# self.right NoneclassSolution:# 返回构造的TreeNode根节点defreConstructBinaryTree(self,pre,tin):# write code hereifnotpre:returnroot_valpre[0]rootTreeNode(root_val)foriinrange(len(tin)):iftin[i]root_val:breakroot.leftself.reConstructBinaryTree(pre[1:1i],tin[:i])root.rightself.reConstructBinaryTree(pre[1i:],tin[i1:])returnroot用两个栈来实现一个队列完成队列的Push和Pop操作。 队列中的元素为int类型。
RELATED

相关推荐

LRC歌词下载神器:一键批量解决离线音乐库同步难题

LRC歌词下载神器:一键批量解决离线音乐库同步难题

LRC歌词下载神器:一键批量解决离线音乐库同步难题 【免费下载链接】lrcget Utility for mass-downloading LRC synced lyrics for your offline music library. 项目地址: https://gitcode.com/gh_mirrors/lr/lrcget 你是否拥有大量本地音乐文件,…

📅 2026/11/17 1:42:46
B. Rolling The Polygon【The 2019 Asia Yinchuan First Round Online Programming】

B. Rolling The Polygon【The 2019 Asia Yinchuan First Round Online Programming】

题目链接:https://nanti.jisuanke.com/t/41286 计蒜课区域赛网络赛:The 2019 Asia Yinchuan First Round Online Programming 样例输入 4 4 0 0 2 0 2 2 0 2 1 1 3 0 0 2 1 1 2 1 1 5 0 0 1 0 2 2 1 3 -1 2 0 0 6 0 0 3 0 4 1 2 2 1 2 -1 1 1 0 样例…

📅 2026/11/15 21:07:37
SpringBoot宠物店管理系统:电商与服务业态融合实践

SpringBoot宠物店管理系统:电商与服务业态融合实践

1. 项目概述:当SpringBoot遇上宠物经济去年帮学弟调试毕业设计时,意外发现宠物店管理系统竟成了计算机专业的热门选题。这个基于SpringBoot的宠物店管理系统之所以备受青睐,关键在于它完美融合了电商系统与服务业态的双重特性。系统前端采用T…

📅 2026/11/16 14:02:16
MORE NEWS

更多资讯

📰

万江电工证怎么考证 通过官方报名入口避开中介陷阱

万江电工证怎么考证 通过官方报名入口避开中介陷阱 你是不是也遇到过这种情况:想考电工证,但不知道去哪里报名,怕被中介骗钱?别担心,这篇文章就来帮你理清楚【万江电工证怎么考证】的全流程,重点讲清楚 官方报名入口 在哪里,怎么报名才不会被坑。…

📰

支线电工作业上岗必备:新手怎么考证才能顺利上岗?

支线电工作业上岗必备:新手怎么考证才能顺利上岗? 你是不是也遇到过这种情况:手里拿着电工证,却被告知不能上岗?不是因为技术不行,而是因为 支线电工作业证 没拿到!这个证书现在成了很多电工岗位的 上岗必备…

📰

金宝考电工证多少钱通过率揭秘,报名别被中介坑了

金宝考电工证多少钱通过率揭秘,报名别被中介坑了 你是不是也遇到过这种情况:想考个电工证,到处打听信息,结果越打听越迷糊,中介报价五花八门,靠谱的机构根本找不到?别急,今天咱们就来聊聊“ 金宝考电工证多少钱 ”这个问题,顺便揭开它的…

📰

工地太忙根本没时间复习考试?泾阳电工证怎么考有考前押题攻略

工地太忙根本没时间复习考试?泾阳电工证怎么考有考前押题攻略 工地太忙根本没时间复习考试?我理解你的焦虑,作为漯河一家中小施工企业的负责人,我也经历过类似的困扰。尤其是现在特种作业操作证的监管越来越严格, 泾阳电工证怎么考…

📰

梅州电工证在哪里年审怎么通过?电子证书怎么查?别再交冤枉钱!

梅州电工证在哪里年审怎么通过?电子证书怎么查?别再交冤枉钱! 怕考不过白交培训费?梅州电工证年审流程复杂,很多学员一头雾水,培训费花了不说,还怕挂科白忙一场。其实只要掌握正确的方法,年审并不是难事,特别是现在 电子证书…

📰

电工证在网上哪查证怎么转异地真实经历告诉你别怕考不过白交培训费

电工证在网上哪查证怎么转异地真实经历告诉你别怕考不过白交培训费 怕考不过白交培训费?我认识一个河南开封的转岗电工,之前在工地干了五年,去年准备报考低压电工证,结果被培训机构忽悠交了三千多培训费,考了两次都没过,最后连报名费都没退。这事儿我亲…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬