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

力扣刷题-二叉树-二叉树最小深度

给定一个二叉树,找出其最小深度。
最小深度是从根节点最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。(注意题意)
示例 1:
image.png
输入:root = [3,9,20,null,null,15,7]
输出:2

层序遍历法
# 层序遍历法
class Solution(object):def minDepth(self, root):""":type root: TreeNode:rtype: int"""if not root:return 0queue = deque([(root, 1)]) # 每个元素是元组 一个是树元素值 一个是最小深度 比较巧妙while queue:cur, min_depth = queue.popleft()if not cur.left and not cur.right:return min_depthif cur.left:queue.append((cur.left, min_depth+1))if cur.right:queue.append((cur.right, min_depth+1))return 0

时间复杂度:O(N) 因为每个结点会访问一次
空间复杂度:O(N)在层序遍历法中空间复杂度主要取决于队列的开销,队列中的元素个数不会超过树的节点数。

递归法

注意这块和最大深度不一样,如下是错误代码:说明:叶子节点是指没有子节点的节点。(注意题意)
image.png
这个代码就犯了此图中的误区:说明:叶子节点是指没有子节点的节点。(注意题意)
image.png
如果这么求的话,没有左孩子的分支会算为最短深度。
所以,如果左子树为空,右子树不为空,说明最小深度是 1 + 右子树的深度。
反之,右子树为空,左子树不为空,最小深度是 1 + 左子树的深度。 最后如果左右子树都不为空,返回左右子树深度最小值 + 1 。
image.png

# 递归法
class Solution(object):def minDepth(self, root):""":type root: TreeNode:rtype: int"""return self.getDepth(root)def getDepth(self, node):if node is None:return 0leftDepth = self.getDepth(node.left)  # 左rightDepth = self.getDepth(node.right)  # 右# 中# 当一个左子树为空,右不为空,这时并不是最低点if node.left is None and node.right is not None:return 1 + rightDepth# 当一个右子树为空,左不为空,这时并不是最低点if node.left is not None and node.right is None:return 1 + leftDepthresult = 1 + min(leftDepth, rightDepth)return result

时间复杂度:O(N),其中 N 是树的节点数。对每个节点访问一次。
空间复杂度:O(N)/O(H) 其中 H 是树的高度。空间复杂度主要取决于递归时栈空间的开销,最坏情况下,树呈现链状,空间复杂度为 O(N)。平均情况下树的高度与节点数的对数正相关,空间复杂度为 O(log⁡N)

参考:
https://www.programmercarl.com/0111.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6.html

http://www.lryc.cn/news/237593.html

相关文章:

  • 注解方式优雅的实现 Redisson 分布式锁
  • PHP/Laravel通过经纬度计算距离获取附近商家
  • grafana面板介绍
  • 实验三 循环结构程序设计(Python)
  • Flutter笔记:目录与文件存储以及在Flutter中的使用(上)
  • 注意了!申请流量卡时地址一定不要填写学校,不好下卡哦!
  • minio使用shell上传文件
  • LeetCode538. Convert BST to Greater Tree
  • iPaaS和RPA,企业自动化应该如何选择?
  • AI实践与学习1_Milvus向量数据库实践与原理分析
  • 3Dexcite deltgen 2022x 新功能
  • 代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形
  • 【2023云栖】陈守元:阿里云开源大数据产品年度发布
  • Element UI 禁用数字输入框组件添加鼠标滚动事件
  • 担忧CentOS停服?KeyarchOS系统来支撑
  • 聚观早报 |联想集团Q2财季业绩;小鹏汽车Q3营收
  • SAP ABAP权限控制中常用TCODE
  • 云计算赛项容器云2023搭建
  • 11.1 文件拷贝移动与删除
  • redhat下使用CentOS yum源,并安装docker
  • 基于单片机体温脉搏检测控制系统及源程序
  • MyBatis-Plus逻辑删@TableLogic
  • 本地私域线上线下 线上和线下的小程序
  • 【前端学java】java中的Object类(8)
  • TensorFlow实战教程(二十六)-什么是生成对抗网络GAN?基础原理和代码普及
  • IDEA版SSM入门到实战(Maven+MyBatis+Spring+SpringMVC) -Maven依赖管理,版本号管理,继承和聚合
  • OpenVPN Connect使用连接公网VPN服务器实现内网穿透
  • Redis(集合Set和有序集合SortedSet)
  • 黔院长 | 《黄帝内经》——奇病论!
  • 手撕单链表(C语言)