当前位置: 首页 > news >正文

承德项目网/seo就业指导

承德项目网,seo就业指导,专业做网站建设制作服务,黑龙江网站设计判断一个树是不是平衡二叉树 方法1 递归 对于某个节点。求其左右子树的高度差,如果满足,再递归的判断左右子树。这是一种自顶而下的方法 class Solution1:def isBalanced(self, root):""":type root: TreeNode:rtype: bool""…

在这里插入图片描述
判断一个树是不是平衡二叉树

方法1 递归

对于某个节点。求其左右子树的高度差,如果满足,再递归的判断左右子树。这是一种自顶而下的方法

class Solution1:def isBalanced(self, root):""":type root: TreeNode:rtype: bool"""if root == None:return Trueelse:if abs(self.getHeight(root.left) -  self.getHeight(root.right)) <=1:return  self.isBalanced(root.left) and self.isBalanced(root.right)else:return Falsedef getHeight(self, root):if root == None:return 0else:return max(self.getHeight(root.left), self.getHeight(root.right))+1

方法2 改进版递归

上面的方法重复计算了很多节点的深度,我们可以自底向上,如果不满足就返回-1,判断根节点的返回值即可。

class Solution2:def isBalanced(self, root):""":type root: TreeNode:rtype: bool"""return self.getHeight(root) != -1def  getHeight(self,root):if root == None:return 0l = self.getHeight(root.left)if l == -1:return -1r = self.getHeight(root.right)if r == -1:return -1if abs(l - r) > 1:return -1else:return max(l, r)+1

方法三 非递归 需要修改节点的val

非递归法主要通过栈来完成,是一个自底向上的过程,最难的过程就是子节点的深度确定后如何确定父节点的深度
一个方法是修改节点的值为该节点自底向上的深度,即方法三
另一个方法就是讲节点的深度保存到一个map里,即方法四

class Solution3:def isBalanced(self, root):""":type root: TreeNode:rtype: bool"""if root == None:return Truestack = []prev = NonepNode = rootwhile(len(stack) or pNode):if pNode != None:stack.append(pNode)pNode = pNode.leftelse:pNode = stack[-1]if pNode.right == prev or pNode.right == None:stack.pop()prev = pNodeif pNode.left == None or pNode.right == None:if pNode.left == None and pNode.right == None:pNode.val = 1else:node = pNode.left if pNode.left != None else pNode.rightif node.val >=2:return FalsepNode.val = node.val +1else:l = pNode.left.valr = pNode.right.valif abs(l -r) >1 :return Falseelse:pNode.val  = max(pNode.left.val, pNode.right.val) +1pNode = Noneelse:pNode = pNode.rightreturn True

方法四 非递归 map作为辅助空间

class Solution4:def isBalanced(self, root):""":type root: TreeNode:rtype: bool"""pNode, prev, dictionary, stack = root, None, {}, []while(len(stack) or pNode):if pNode:stack.append(pNode)pNode = pNode.leftelse:pNode = stack[-1]if pNode.right == None or pNode.right == prev:stack.pop()l = dictionary.get(pNode.left, 0)r = dictionary.get(pNode.right, 0)if abs(l - r) > 1:return Falseelse:dictionary[pNode] = max(l, r) +1prev =  pNodepNode = Noneelse:pNode = pNode.rightreturn True
http://www.lbrq.cn/news/1560817.html

相关文章:

  • 妈妈在家里做女视频网站/天津seo推广
  • 湛江网站开发/网络工程师是干什么的
  • 池州网站建设公司/类似58的推广平台有哪些平台
  • 百度抓取网站/百度 seo 工具
  • 石家庄网站建设公司哪个好/百度视频推广怎么收费
  • wordpress 文章标签 调用/东莞网站关键词优化排名
  • 网站开发的app/长沙 建站优化
  • 外贸soho建网站/上海知名网站制作公司
  • 代加工厂接单平台/优化大师apk
  • 做英文网站公司/长沙网站排名推广
  • 电商设计网站素材/亚马逊排名seo
  • wordpress 显示空白页/广州seo外包多少钱
  • 网站优化的监测评估/seo排名优化软件免费
  • 中山做网站费用/深圳网站优化培训
  • 销售网站开发步骤/怎么样免费做网站
  • 建设银行泰安培训中心官方网站/广州官方新闻
  • 网站开发和软件开发/如何自己建个网站
  • 手机网站欣赏/深圳全网推广平台
  • 双鸭山住房和城乡建设局网站/互动营销公司
  • 呼和浩特商城网站建设/一键生成个人网站
  • 企业网络服务平台/独立站seo建站系统
  • word做网站框架/网站seo什么意思
  • 网站备案入口/百度广告
  • 热点 做网站和营销 我只服他/网络运营需要学什么
  • 罗岗网站建设公司/关键词优化骗局
  • 关于加强政府网站建设的通知/企业网站制作多少钱
  • ui中国网站/石家庄邮电职业技术学院
  • 宜昌网站建设哪家好/百度竞价推广投放
  • access做网站服务器/新闻今日头条最新消息
  • 如何上传自己做的网站/seo自动优化工具
  • 电路方案分析(二十二)适用于音频应用的25-50W反激电源方案
  • SysTick寄存器(嘀嗒定时器实现延时)
  • ISO27001 高阶架构 之 支持 -2
  • 2025年生成式引擎优化(GEO)服务商技术能力评估报告
  • Flutter Provider 模式实现:基于 InheritedWidget 的状态管理实现
  • 系统时钟配置