leetcode尊享面试——二叉树(python)

2024-05-06 14:20

本文主要是介绍leetcode尊享面试——二叉树(python),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

250.统计同值子树

使用dfs深度搜索,同值子树,要满足三个条件:

对于当前节点node,他的左子树血脉纯净(为同值子树),右子树血脉纯净(为同值子树),node的值等于左右子树节点的值。

全是if判断,推理!!!

class Solution:def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:n, b = self.dfs(root)return ndef dfs(self, root):if not root: return 0, Truen = 0b = Truen1, b1 = self.dfs(root.left)n2, b2 = self.dfs(root.right)n = n1 + n2if not b1 or not b2:b = Falseif root.left and root.left.val != root.val:b = Falseif root.right and root.right.val != root.val:b = Falseif b: n += 1return n, b

1120.子树的最大平均值

使用dfs, 返回以root为根的所以节点的总和,节点数量。

没有任何技巧,全是感情!!!

class Solution:def __init__(self):self.m = 0def maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:self.dfs(root)return self.mdef dfs(self, root):# 返回以root为根的所以节点的总和,节点数量if not root: return 0, 0s1, c1 = self.dfs(root.left)s2, c2 = self.dfs(root.right)s = s1 + s2 + root.valc = c1 + c2 + 1self.m = max(self.m, s/c)return s, c

545.二叉树的边界

 可以把题目分成三个问题,使用三个dfs解决,可以发现左边界和右边界很相似,dfs传入一个idx判断是先从左走还是先从右走,另外题目说:根节点 不是 叶节点。但是数据中存在只有一个节点的情况需要注意。

class Solution:def __init__(self):self.leaf = []def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:if not root.left and not root.right: return [root.val]ans = []if root.left:l = self.find_ls(root, 0)ans += lelse:ans = [root.val]self.find_leaf(root)ans += self.leafif root.right:r = self.find_ls(root, 1)ans += r[::-1]ans.pop()return ansdef find_ls(self, root, idx):ans = [root.val]if idx == 1:root.left, root.right = root.right, root.leftif root.left:ans += self.find_ls(root.left, idx)elif root.right:ans += self.find_ls(root.right, idx)else:return []return ansdef find_leaf(self, root):if root.left:self.find_leaf(root.left)if root.right:self.find_leaf(root.right)if not root.left and not root.right:self.leaf.append(root.val)

366.寻找二叉树的叶子节点

任然使用dfs深度搜索,记录每一层的位置,然后在ans相应位置中插入

class Solution:def __init__(self):self.length = 0self.ans = []def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:self.dfs(root)return self.ansdef dfs(self, root):if not root: return 0n1 = self.dfs(root.left)n2 = self.dfs(root.right)n = max(n1, n2)if self.length - 1 < n:self.length += 1self.ans.append([])self.ans[n].append(root.val)return n + 1

还能补充知识吗!!!我的大脑🧠

这篇关于leetcode尊享面试——二叉树(python)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/964591

相关文章

利用python实现对excel文件进行加密

《利用python实现对excel文件进行加密》由于文件内容的私密性,需要对Excel文件进行加密,保护文件以免给第三方看到,本文将以Python语言为例,和大家讲讲如何对Excel文件进行加密,感兴... 目录前言方法一:使用pywin32库(仅限Windows)方法二:使用msoffcrypto-too

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

python获取网页表格的多种方法汇总

《python获取网页表格的多种方法汇总》我们在网页上看到很多的表格,如果要获取里面的数据或者转化成其他格式,就需要将表格获取下来并进行整理,在Python中,获取网页表格的方法有多种,下面就跟随小编... 目录1. 使用Pandas的read_html2. 使用BeautifulSoup和pandas3.

Python装饰器之类装饰器详解

《Python装饰器之类装饰器详解》本文将详细介绍Python中类装饰器的概念、使用方法以及应用场景,并通过一个综合详细的例子展示如何使用类装饰器,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录1. 引言2. 装饰器的基本概念2.1. 函数装饰器复习2.2 类装饰器的定义和使用3. 类装饰

Python 交互式可视化的利器Bokeh的使用

《Python交互式可视化的利器Bokeh的使用》Bokeh是一个专注于Web端交互式数据可视化的Python库,本文主要介绍了Python交互式可视化的利器Bokeh的使用,具有一定的参考价值,感... 目录1. Bokeh 简介1.1 为什么选择 Bokeh1.2 安装与环境配置2. Bokeh 基础2

如何使用 Python 读取 Excel 数据

《如何使用Python读取Excel数据》:本文主要介绍使用Python读取Excel数据的详细教程,通过pandas和openpyxl,你可以轻松读取Excel文件,并进行各种数据处理操... 目录使用 python 读取 Excel 数据的详细教程1. 安装必要的依赖2. 读取 Excel 文件3. 读

Python的time模块一些常用功能(各种与时间相关的函数)

《Python的time模块一些常用功能(各种与时间相关的函数)》Python的time模块提供了各种与时间相关的函数,包括获取当前时间、处理时间间隔、执行时间测量等,:本文主要介绍Python的... 目录1. 获取当前时间2. 时间格式化3. 延时执行4. 时间戳运算5. 计算代码执行时间6. 转换为指

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模