代码随想录算法训练营第十八天(py)| 二叉树 | 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

本文主要是介绍代码随想录算法训练营第十八天(py)| 二叉树 | 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

654.最大二叉树

力扣链接
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:
二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树,并且输出这个树的根节点。

思路

构建树一般采用前序遍历,因为先构造中间节点,然后递归构造左子树和右子树。

class Solution:def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:# 如果数组就剩一个元素,就是到叶子节点了# 定义一个新节点if len(nums)==1:return TreeNode(nums[0]) # 1.找到数组中最大的值和对应的下标, 用最大的值构造根节点node = TreeNode(0)maxval = 0maxvalidx = 0for i in range(len(nums)):if nums[i]>maxval:maxval = nums[i]maxvalidx = inode.val = maxval# 2.最大值左边的元素构建左子树if maxvalidx > 0:left_list = nums[:maxvalidx]node.left = self.constructMaximumBinaryTree(left_list)# 3.最大值右边的元素构建右子树if maxvalidx < len(nums)-1:right_list = nums[maxvalidx+1:]node.right = self.constructMaximumBinaryTree(right_list)return node

617.合并二叉树

力扣链接
给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

思路 递归-前序遍历

class Solution:def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:if root1 == None:return root2if root2 == None:return root1# 定义一个新树的根节点root = TreeNode(0)root.val = root1.val + root2.valroot.left = self.mergeTrees(root1.left, root2.left)root.right = self.mergeTrees(root1.right, root2.right)return root

700.二叉搜索树中的搜索

力扣链接
给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。
BST的特性为左边的比中间大,右边的比中间小,且BST的子树依旧是BST。

思路1 递归

class Solution:def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:if root == None or root.val == val:return root# val小,要找的值在左边if root.val > val:return self.searchBST(root.left,val)# val大,要找的值在右边        if root.val < val:return self.searchBST(root.right,val)

思路2 迭代

class Solution:def searchBST(self, root: TreeNode, val: int) -> TreeNode:while root:if val < root.val: root = root.leftelif val > root.val: root = root.rightelse: return rootreturn None

98.验证二叉搜索树

力扣链接
给定一个二叉树,判断其是否是一个有效的二叉搜索树。

思路 中序遍历后判断是否有序

class Solution:def isValidBST(self, root: Optional[TreeNode]) -> bool:res = []def dfs(node):if node is None:returndfs(node.left)res.append(node.val)dfs(node.right)dfs(root)for i in range(1,len(res)):if res[i]<=res[i-1]:return Falsereturn True

这篇关于代码随想录算法训练营第十八天(py)| 二叉树 | 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1008372

相关文章

IDEA实现回退提交的git代码(四种常见场景)

《IDEA实现回退提交的git代码(四种常见场景)》:本文主要介绍IDEA实现回退提交的git代码(四种常见场景),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1.已提交commit,还未push到远端(Undo Commit)2.已提交commit并push到

Kotlin Compose Button 实现长按监听并实现动画效果(完整代码)

《KotlinComposeButton实现长按监听并实现动画效果(完整代码)》想要实现长按按钮开始录音,松开发送的功能,因此为了实现这些功能就需要自己写一个Button来解决问题,下面小编给大... 目录Button 实现原理1. Surface 的作用(关键)2. InteractionSource3.

使用Java实现Navicat密码的加密与解密的代码解析

《使用Java实现Navicat密码的加密与解密的代码解析》:本文主要介绍使用Java实现Navicat密码的加密与解密,通过本文,我们了解了如何利用Java语言实现对Navicat保存的数据库密... 目录一、背景介绍二、环境准备三、代码解析四、核心代码展示五、总结在日常开发过程中,我们有时需要处理各种软

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

Java 压缩包解压实现代码

《Java压缩包解压实现代码》Java标准库(JavaSE)提供了对ZIP格式的原生支持,通过java.util.zip包中的类来实现压缩和解压功能,本文将重点介绍如何使用Java来解压ZIP或RA... 目录一、解压压缩包1.zip解压代码实现:2.rar解压代码实现:3.调用解压方法:二、注意事项三、总

Linux实现简易版Shell的代码详解

《Linux实现简易版Shell的代码详解》本篇文章,我们将一起踏上一段有趣的旅程,仿照CentOS–Bash的工作流程,实现一个功能虽然简单,但足以让你深刻理解Shell工作原理的迷你Sh... 目录一、程序流程分析二、代码实现1. 打印命令行提示符2. 获取用户输入的命令行3. 命令行解析4. 执行命令

利用Python实现Excel文件智能合并工具

《利用Python实现Excel文件智能合并工具》有时候,我们需要将多个Excel文件按照特定顺序合并成一个文件,这样可以更方便地进行后续的数据处理和分析,下面我们看看如何使用Python实现Exce... 目录运行结果为什么需要这个工具技术实现工具的核心功能代码解析使用示例工具优化与扩展有时候,我们需要将

SQL Server身份验证模式步骤和示例代码

《SQLServer身份验证模式步骤和示例代码》SQLServer是一个广泛使用的关系数据库管理系统,通常使用两种身份验证模式:Windows身份验证和SQLServer身份验证,本文将详细介绍身份... 目录身份验证方式的概念更改身份验证方式的步骤方法一:使用SQL Server Management S

uniapp小程序中实现无缝衔接滚动效果代码示例

《uniapp小程序中实现无缝衔接滚动效果代码示例》:本文主要介绍uniapp小程序中实现无缝衔接滚动效果的相关资料,该方法可以实现滚动内容中字的不同的颜色更改,并且可以根据需要进行艺术化更改和自... 组件滚动通知只能实现简单的滚动效果,不能实现滚动内容中的字进行不同颜色的更改,下面实现一个无缝衔接的滚动

利用Python实现可回滚方案的示例代码

《利用Python实现可回滚方案的示例代码》很多项目翻车不是因为不会做,而是走错了方向却没法回头,技术选型失败的风险我们都清楚,但真正能提前规划“回滚方案”的人不多,本文从实际项目出发,教你如何用Py... 目录描述题解答案(核心思路)题解代码分析第一步:抽象缓存接口第二步:实现两个版本第三步:根据 Fea