C++数据结构与算法——二叉搜索树的属性

C++第二阶段——数据结构和算法,之前学过一点点数据结构,当时是基于Python来学习的,现在基于C++查漏补缺,尤其是树的部分。这一部分计划一个月,主要利用代码随想录来学习,刷题使用力扣网站,不定时更新,欢迎关注!

文章目录

  • 一、二叉搜索树中的搜索(力扣700)
  • 二、验证二叉搜索树(力扣98)
  • 三、二叉搜索树的最小绝对差(力扣530)
  • 四、二叉搜索树中的众数(力扣501)
  • 五、把二叉搜索树转换为累加树(力扣538)

一、二叉搜索树中的搜索(力扣700)

在这里插入图片描述

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(root==NULL||root->val==val) return root;TreeNode * result;if(root->val<val){// 找右子树result = searchBST(root->right,val);}else{result = searchBST(root->left,val);}return result;}
};

在这里插入图片描述

二、验证二叉搜索树(力扣98)

在这里插入图片描述

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* pre = NULL;bool isValidBST(TreeNode* root) {// 使用二叉搜索树的特征,即使用线序遍历,pre结点的值总是比cur结点的值小if(root==NULL) return true;bool left = isValidBST(root->left);if(pre!=NULL){if(pre->val>=root->val){return false;}}pre = root;bool right = isValidBST(root->right);return left&&right;}
};

在这里插入图片描述

三、二叉搜索树的最小绝对差(力扣530)

在这里插入图片描述

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int minNum = INT_MAX;TreeNode * pre=NULL;int result;void traversal(TreeNode * root){// 类似于判断二叉搜索树,使用pre和cur结点if(root==NULL) return;// 左中右traversal(root->left);if(pre!=NULL){if(root->val-pre->val<minNum){minNum = root->val-pre->val;}}pre = root;traversal(root->right);result = minNum;}int getMinimumDifference(TreeNode* root) {traversal(root);return result;}
};

在这里插入图片描述

四、二叉搜索树中的众数(力扣501)

在这里插入图片描述

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode * pre=NULL;int count;int maxN =0;vector<int> findMode(TreeNode* root) {// 同样使用双指针的思想 统计众数vector<int> result;traversal(root,result);return result;}void traversal(TreeNode* root,vector<int>& result){if(root==NULL) return;//左traversal(root->left,result);//中if(pre==NULL) count =1;else if(root->val!=pre->val) count=1;else count+=1;// 更新结点pre = root;if(count>maxN){maxN = count;result.clear();result.push_back(root->val);}else if(count==maxN){result.push_back(root->val);}// 右traversal(root->right,result);      // 右return ;}
};

在这里插入图片描述

五、把二叉搜索树转换为累加树(力扣538)

在这里插入图片描述

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int pre=0;TreeNode* convertBST(TreeNode* root) {if(root==NULL) return NULL;// 右中左遍历 从小到大convertBST(root->right);root->val += pre;// 更新prepre = root->val;convertBST(root->left);return root;}
};

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

获取PDF中的布局信息——如何获取段落

PDF解析是极其复杂的问题。不可能靠一个工具解决全部问题&#xff0c;尤其是五花八门&#xff0c;格式不统一的PDF文件。除非有钞能力。如果没有那就看看可以分为哪些问题。 提取文本内容&#xff0c;提取表格内容&#xff0c;提取图片。我认为这些应该是分开做的事情。python有…

[VNCTF2024]-PWN:preinit解析(逆向花指令,绕过strcmp,函数修改,机器码)

查看保护&#xff1a; 查看ida&#xff1a; 这边其实看反汇编没啥大作用&#xff0c;需要自己动调。 但是前面的绕过strcmp还是要看一下的。 解题&#xff1a; 这里是用linux自带的产生随机数的文件urandom来产生一个随机密码&#xff0c;然后让我们输入密码&#xff0c;用st…

msvcr120.dll丢失的解决办法的详细步骤,简单有效的解决msvcr120.dll丢失

当我们遇到电脑提示msvcr120.dll文件不见了时&#xff0c;无需过分紧张&#xff0c;因为这个问题有众多解决方案可供我们选择。今天我特意准备了一些应对这一问题的经验分享&#xff0c;并给大家带来一些独到的解决思路。让我们一起来探讨吧&#xff01; 一、先了解一下什么是m…

Swagger3 使用详解

Swagger3 使用详解 一、简介1 引入依赖2 开启注解3 增加一个测试接口4 启动服务报错1.5 重新启动6 打开地址&#xff1a;http://localhost:8093/swagger-ui/index.html 二、Swagger的注解1.注解Api和ApiOperation2.注解ApiModel和ApiModelProperty3.注解ApiImplicitParams和Api…

Huggingface初上手即ERNIE-gram句子相似性实战

大模型如火如荼的今天&#xff0c;不学点语言模型&#xff08;LM&#xff09;相关的技术实在是说不过去了。只不过由于过往项目用到LM较少&#xff0c;所以学习也主要停留在直面——动眼不动手的水平。Huggingface&#xff08;HF&#xff09;也是现在搞LM离不开的工具了。 出于…

k8s pv与pvc理解与实践

参考文章&#xff1a; https://blog.csdn.net/qq_41337034/article/details/117220475 一、 pv/pvc简述 Pv是指PersistentVolume&#xff0c;中文含义是持久化存储卷是对底层的共享存储的一种抽象&#xff0c;Pv由管理员进行配置和创建&#xff0c;只要包含存储能力&#xff…

Rocky Linux 安装部署 Zabbix 6.4

一、Zabbix的简介 Zabbix是一种开源的企业级监控解决方案&#xff0c;用于实时监测服务器、网络设备和应用程序的性能和可用性。它提供了强大的数据收集、处理和可视化功能&#xff0c;同时支持事件触发、报警通知和自动化任务等功能。Zabbix易于安装和配置&#xff0c;支持跨平…

论文阅读:2020GhostNet华为轻量化网络

创新&#xff1a;&#xff08;1&#xff09;对卷积进行改进&#xff08;2&#xff09;加残差连接 1、Ghost Module 1、利用1x1卷积获得输入特征的必要特征浓缩。利用1x1卷积对我们输入进来的特征图进行跨通道的特征提取&#xff0c;进行通道的压缩&#xff0c;获得一个特征浓…

C语言第三十三弹---动态内存管理(上)

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】 动态内存管理 1、为什么要有动态内存分配 2、malloc和free 2.1、malloc 2.2、free 3、calloc和realloc 3.1、calloc 3.2、realloc 4、常见的动态内存的错…

阿里云短信验证笔记

1.了解阿里云的权限操作 进入AccessKey管理 选择子用户 创建用户组和用户 先创建用户组&#xff0c;建好再进行权限分配 添加短信管理权限 创建用户 创建好后的id和密码在此处下载可以得到 2.开通阿里云短信服务 进行申请&#xff0c;配置短信模板 阿里云短信API文档 短信服务…

MySQL 逗号分隔查询--find_in_set()函数

业务场景&#xff1a; 在使用MySQL的时候&#xff0c;可能的某个字段存储的是一个英文逗号分割的字符串&#xff08;这里我们不讨论表设计的合理性&#xff09;&#xff0c;如图所示&#xff1a; 我们在查询的时候需要匹配逗号分割中的某个字符串&#xff0c;该怎么查询呢&am…

地图可视化绘制 | R-ggplot2 NC地图文件可视化

在推出两期数据分享之后&#xff0c;获取数据的小伙伴们也知道&#xff0c;数据格式都是NetCDF(nc) 格式网格数据&#xff0c;虽然我在推文分享中说明使用Python、R或者GIS类软件都是可以进行 处理和可视化绘制的&#xff0c;但是&#xff0c;还是有小伙伴咨询使用编程软件Pyth…

浅谈mysql mvcc

目录 前言 mvcc 是如何工作的&#xff1f; 数据的更新 前言 mvcc 与一个事物的隔离级别有关&#xff0c;未提交读永远读的是当前值&#xff0c;串行化是通过加锁实现&#xff0c;这两种隔离级别都与mvcc 没有任何关系。只要一提到mvcc应该想到的是读提交以及可重复读&#…

Spring八股 常见面试题

什么是Spring Bean 简单来说&#xff0c;Bean 代指的就是那些被 IoC 容器所管理的对象。我们需要告诉 IoC 容器帮助我们管理哪些对象&#xff0c;这个是通过配置元数据来定义的。配置元数据可以是 XML 文件、注解或者 Java 配置类。 将一个类声明为 Bean 的注解有哪些? Com…

【buuctf-gakki】

binwalk 查看图片&#xff0c;发现有 rar 文件&#xff0c;提取后如上图所示&#xff08;flag.txt为已经解压后出来的&#xff09;其中这个 rar 需要用 archpr爆破一下 打开后一个 flag.txt 一堆杂乱无章的字符&#xff0c;需要用到 python 脚本进行词频统计&#xff0c;我们…

Vue3 在SCSS中使用v-bind

template 先创建一个通用的页面结构 <template><div class"v-bubble-bg"></div> </template>js 在JS中先对需要用的数据进行定义&#xff1a; 可以是参数&#xff0c;也可以是data <script setup>const props defineProps({bgCol…

设计模式系列文章-7个创建型模式更新已完结

其实从2019年开始就有些一套关于设计模式的系列文章&#xff0c;但是因为种种原因一直搁置到现在。直到2024年才又恢复更新。 24年1月份上旬一直在弄博客站&#xff1a;https://jaune162.blog 的搭建 24年1月份下旬弄专题站&#xff1a;https://books.jaune162.blog 的搭建。…

本地写的Bash脚本,Linux端运行报错:/bin/bash^M: bad interpreter: No such file or directory

背景 在本地写了个Bash Shell脚本&#xff0c;但上传到Linux端后加完权限执行时报错&#xff1a; &#xff08;脚本名&#xff1a;script.sh&#xff09; -bash: ./script.sh: /bin/bash^M: bad interpreter: No such file or directory 分析 这个错误通常是由于脚本文件的行…

beets,一个有趣的 Python 音乐信息管理工具!

前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站AI学习网站。 目录 前言 什么是Beet库&#xff1f; 安装Beet库 使用Beet库 Beet库的功能特性 1. 多种音乐格式支持 2. 自动标签识…

LNMP架构介绍及配置--部署Discuz社区论坛与wordpress博客

一、LNMP架构定义 1、LNMP定义 LNMP&#xff08;Linux Nginx Mysql Php&#xff09;是指一组通常一起使用来运行动态网站或者服务器的自由软件名称首字母缩写&#xff1b;Linux系统下NginxMySQLPHP这种网站服务器架构。 Linux是一类Unix计算机操作系统的统称&#xff0c;是目…