Python版day16

news/2024/10/30 19:28:20/

104. 二叉树的最大深度

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:if not root:return 0left = self.maxDepth(root.left)right = self.maxDepth(root.right)return max(left,right) + 1

111. 二叉树的最小深度

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明:叶子节点是指没有子节点的节点

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def minDepth(self, root: Optional[TreeNode]) -> int:if not root:return 0left = self.minDepth(root.left)right = self.minDepth(root.right)if not root.left and root.right:return 1+rightif not root.right and root.left:return 1+leftreturn min(left,right)+1

 要注意:叶子节点是指没有左右子节点的节点。那么就不能无脑return min(left,right)+1 因为如果左边是空右边不是空那么会直接返回1而不是右边的长度

222. 完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。

完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/count-complete-tree-nodes
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

暴力解法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def countNodes(self, root: Optional[TreeNode]) -> int:if not root:return 0res = []queue = deque()queue.append(root)while queue:size = len(queue)for i in range(0, size):node = queue.popleft()res.append(node)if node.left:queue.append(node.left)if node.right:queue.append(node.right)return len(res)

普通二叉树写法 递归 卧槽比循环还慢!

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def countNodes(self, root: Optional[TreeNode]) -> int:if not root:return 0left = self.countNodes(root.left)right = self.countNodes(root.right)return 1+left+right

完全二叉树写法 递归 更tm慢了

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def countNodes(self, root: Optional[TreeNode]) -> int:if not root: return 0count = 1left = root.leftright = root.rightwhile left and right:count +=1left = left.leftright = right.rightif not left and not right: # 如果同时到底说明是满二叉树return 2**count-1return 1+self.countNodes(root.left)+self.countNodes(root.right)


http://www.ppmy.cn/news/396740.html

相关文章

一键式 RLHF 训练 DeepSpeed Chat(二):实践篇

一键式 RLHF 训练 DeepSpeed Chat(二):实践篇 之前给大家分享了一键式 RLHF 训练 DeepSpeed Chat(一):理论篇,本文给大家分享如何使用DeepSpeed Chat进行RLHF训练。 DeepSpeed Chat 的 RLHF 训…

Servlet相关介绍

一、什么是servlet Java Servlet 是运行在Web服务器或应用服务器上的程序,使用Servlet可以收集来自网页表单的用户输入,呈现来自数据库或者其它源的记录,还可以动态创建网页。 web服务器只能处理静态的资源,不能处理动态的页面&am…

Could not resolve ‘cn.archive.ubuntu.com‘ ubuntu

add nameserver field in /etc/resolv.confnameserver 8.8.8.8

【华为OD机试】 阿里巴巴找黄金宝箱(Ⅲ)【2023 B卷|100分】

【华为OD机试】-真题 !!点这里!! 【华为OD机试】真题考点分类 !!点这里 !! 题目描述 一贫如洗的樵夫阿里巴巴在去砍柴的路上,无意中发现了强盗集团的藏宝地, 藏宝地有编号从0-N的箱子,每个箱子上面贴有一个数字。 阿里巴巴念出一个咒语数字,查看宝箱是否存在两个不同…

解释什么是 Resizable BAR、如何实现它,并介绍它将如何影响性能。

什么是可调整大小的栏?如何为我的系统启用它? intel A770显卡运行时要求开启Resizable BAR,否则性能据说会损失40%。 其实我测试了下,没有启用之前鲁大师跑分44万,启用后也高不到哪里去,就是个48万。 但是…

Invalid bound statement (not found)出现原因和解决方法

https://blog.csdn.net/weixin_44695793/article/details/107752054?utm_mediumdistribute.pc_relevant.none-task-blog-baidujs_title-0&spm1001.2101.3001.4242

执行bat文件提示:“不是内部或外部命令,也不是可运行的程序或批处理文件”

双击bat文件,出现以下错误提示: 原因:文件不支持UTF-8编码和Unix格式,要选择ANSI编码和Windows格式。 解决:(1) 用Notepad打开bat文件,双击下方的Unix(LF)选择"转换为Windows格式"; (…

TORCH MAXIMUM

import torcha torch.tensor((1, 2, -1)) b torch.tensor((3, 0, 4)) torch.maximum(a, b) 结果应该是: tensor([3, 2, 4]) AttributeError: module torch has no attribute maximum torch版本:1.6.0cu101 发现max和maximum结果一样: print(torch…