【leetcode100-042/043】【二叉树】二叉搜索树的转换和验证

2024-01-20 06:36

本文主要是介绍【leetcode100-042/043】【二叉树】二叉搜索树的转换和验证,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【转换】

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

思路:

可以说是递归板子题了。每次把数组切两半,中间数据拿来做根节点,左边部分继续建左子树,右边部分继续建右子树,只需要注意更改传入的参数就好啦。

class Solution {
public:TreeNode* makeTree(vector<int>& nums,int l, int r){if(l>r) return nullptr;int mid=(l+r)/2;TreeNode* root = new TreeNode(nums[mid]);root->left=makeTree(nums,l,mid-1);root->right=makeTree(nums,mid+1,r);return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {return makeTree(nums,0,nums.size()-1);}
};

【验证】

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

思路:

一开始写了个经典错误版,也就是在判断环节只验证了左右孩子和父节点的关系是否合法,但我们要的其实是左子树所有节点都必须合法。

为此我们引入一个上下界的概念。通过传参实时地限定当前子树中所有节点的合法取值范围。

显然,对某个节点的左子树来说,其下界和以该节点为根节点的整个二叉树是相同的,而其上界则是该节点自身的值,右子树同理,只是改变的是下界。

虽说是整个子树的上下界,但我们只要检查左右孩子就可以,因为递归函数会帮助我们检查到所有的节点,而越小的子树其上下界范围只会越严格,所以不可能出现某节点在小子树时合法而在更大的子树中非法的情况。

class Solution {
public:bool check(TreeNode* root, long long lower, long long upper) {if (root == nullptr)return true;return (root->val > lower) && (root->val < upper) &&check(root->left, lower, root->val) &&check(root->right, root->val, upper);}bool isValidBST(TreeNode* root) { return check(root, LONG_MIN, LONG_MAX); }
};

这篇关于【leetcode100-042/043】【二叉树】二叉搜索树的转换和验证的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

在java中如何将inputStream对象转换为File对象(不生成本地文件)

《在java中如何将inputStream对象转换为File对象(不生成本地文件)》:本文主要介绍在java中如何将inputStream对象转换为File对象(不生成本地文件),具有很好的参考价... 目录需求说明问题解决总结需求说明在后端中通过POI生成Excel文件流,将输出流(outputStre

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

利用Python开发Markdown表格结构转换为Excel工具

《利用Python开发Markdown表格结构转换为Excel工具》在数据管理和文档编写过程中,我们经常使用Markdown来记录表格数据,但它没有Excel使用方便,所以本文将使用Python编写一... 目录1.完整代码2. 项目概述3. 代码解析3.1 依赖库3.2 GUI 设计3.3 解析 Mark

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

Java实现XML与JSON的互相转换详解

《Java实现XML与JSON的互相转换详解》这篇文章主要为大家详细介绍了如何使用Java实现XML与JSON的互相转换,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. XML转jsON1.1 代码目的1.2 代码实现2. JSON转XML3. JSON转XML并输出成指定的

Java实现将Markdown转换为纯文本

《Java实现将Markdown转换为纯文本》这篇文章主要为大家详细介绍了两种在Java中实现Markdown转纯文本的主流方法,文中的示例代码讲解详细,大家可以根据需求选择适合的方案... 目录方法一:使用正则表达式(轻量级方案)方法二:使用 Flexmark-Java 库(专业方案)1. 添加依赖(Ma

Java实现将byte[]转换为File对象

《Java实现将byte[]转换为File对象》这篇文章将通过一个简单的例子为大家演示Java如何实现byte[]转换为File对象,并将其上传到外部服务器,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言1. 问题背景2. 环境准备3. 实现步骤3.1 从 URL 获取图片字节数据3.2 将字节数组

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

Python使用PIL库将PNG图片转换为ICO图标的示例代码

《Python使用PIL库将PNG图片转换为ICO图标的示例代码》在软件开发和网站设计中,ICO图标是一种常用的图像格式,特别适用于应用程序图标、网页收藏夹图标等场景,本文将介绍如何使用Python的... 目录引言准备工作代码解析实践操作结果展示结语引言在软件开发和网站设计中,ICO图标是一种常用的图像