【小浩算法 BST与其验证】

BST与其验证

  • 前言
  • 我的思路
    • 思路一 中序遍历+判断数组无重复递增
    • 思路二 递归+边界最大值最小值的传递
  • 我的代码
    • 测试用例1
    • 测试用例2

前言

BST是二叉树一个经典应用，我们常常将其用于数据的查找以及构建平衡二叉树等。今天我所做的题目是验证一颗二叉树是否为二叉搜索树，应该还算是基础题吧。

我的思路

其实最开始这个题目我的思路并不清晰，基本上只能想到去用递归，但是如何去构建递归的子问题，我想不太到，哈哈哈还是算法小白呢，想不到很正常（偷偷安慰自己…）。思路学习链接：
小浩算法-BST验证
力扣–验证二叉搜索树【98】

思路一 中序遍历+判断数组无重复递增

这个思路我觉得很巧妙，因为它利用了一个特性：二叉搜索树的中序遍历得到的一定是一个完全递增的序列（我们考虑的是二叉树里面无重复值）,随后我们只需要判断一下遍历的结果是否严格递增就好了。总结一下：

  • 先中序遍历BST把结果存储在一个vector里面。
  • 判断该vector是否严格递增。
//验证是否为二叉搜索树
	void isBST(node* root) {
		//先创建一个数组
		vector<char> midOrderArr;
		midOrder(root, midOrderArr);
		//输出看一下我的数组里面存的是不是中序遍历的值
		for (int i = 0; i < midOrderArr.size(); i++) {
			cout << midOrderArr[i] << ' ';
		}
		cout << endl;
		for (int i = 0; i < midOrderArr.size()-1; i++) {
			if (midOrderArr[i] >= midOrderArr[i + 1]) {
				cout << "该二叉树 不是一颗二叉搜索树！" << endl;
				return;
			}
		}
		cout << "该二叉树 是一颗二叉搜索树！" << endl;
	}

	//二叉树的中序遍历
	void midOrder(node* root,vector<char>& Arr) {
		if (root == nullptr) {
			return;
		}
		midOrder(root->left, Arr);
		Arr.push_back(root->info);
		midOrder(root->right, Arr);
	}

思路二 递归+边界最大值最小值的传递

这个题目有一个很有意思的陷阱，那就是我们不光要求 一个结点的左孩子比它小，右孩子比它大。我们要求的是，这个结点的左子树上的所有结点都比它小，右子树上的所有结点都比他大。

因此在递归的时候，我们需要一个上界和下界。
首先需要考虑初始化的问题，这里我们用到climits库里面的LONG_MAX和LONG_MIN.代表long long 类型的最大值和最小值。
递归左子树，上界是根节点的值，下界就选上一层的min ；递归右子树，下界是根节点的值，上界就选上一层的max。perfect！完美！

bool isBST_Recursion(node* root,long long min,long long max) {
		if (root == nullptr) {
			return true;
		}
		if (root->info <= min || root->info >=max) {
			//cout << "该二叉树不是一个二叉搜索树";
			return false;
		}
		return isBST_Recursion(root->left, min, root->info) && isBST_Recursion(root->right, root->info, max);
	}

我的代码

测试用例1

1248##9##5##36##7##

在这里插入图片描述

测试用例2

421##3##65##7##

在这里插入图片描述

#include <iostream>
#include<algorithm>
#include<cmath>
#include <queue> 
#include<climits>
using namespace std;

struct node {
	char info;
	node* left;
	node* right;
	node(char data) :info(data), left(nullptr), right(nullptr) {

	};
	node() :info(NULL), left(nullptr), right(nullptr) {

	};
};

class binaryTree {
private:
		node* root;
public:
	binaryTree() {
		root = new node(NULL);
	}

	//得到树的根结点
	node* getRoot() {
		return root;
	}

	//以递归的方式构建一棵树
	void createTree(node*& t) {
		char str;
		cin >> str;
		if (str == '#') {
			t = NULL;
		}
		else {
			t = new node;//为t开辟空间
			t->info = str;
			createTree(t->left);
			createTree(t->right);
		}
	}

	//树的深度
	int depth(node* root) {
		if (root == nullptr) {
			return 0;
		}
		int left = depth(root->left);
		int right = depth(root->right);
		return max(left, right) + 1;
	}

	//打印一棵树满二叉树，只能打印满二叉树，节点数目最好不要超过10
	void print(node*& root) {
		//存放打印的二叉树
		char str[10][100] = {};
		queue<node*> q;
		int h = depth(root);
		q.push(root);
		int index = 0;
		while (!q.empty()) {
			int size = q.size();
			//存放每一层的节点
			vector<char> list;
			for (int i = 0; i < size; i++) {
				node* temp = q.front();
				q.pop();
				list.push_back(temp->info);
				//cout << temp->info;
				if (temp->left != nullptr) {
					q.push(temp->left);
				}
				if (temp->right != nullptr) {
					q.push(temp->right);
				}
			}
			bool flag = true;
			int j = 0;
			//打印前面部分空白
			while (j <= 2 * h - 1 - index) {
				str[index][j] = ' ';
				j++;

			}
			//保持第一行居中
			if (index == 0) {
				for (int m = 0; m < h - 2; m++) {
					str[index][j++] = ' ';
				}
			}

			for (int k = 0; k < list.size(); k++) {
				//如果是一层最后一个节点
				if (k == list.size() - 1) {
					str[index][j++] = list[k];
				}
				else {
					//相邻左右子节点
					if (k % 2 == 0) {
						str[index][j++] = list[k];
						for (int l = 0; l < 3 + 2 * (h - index / 2 - 1); l++) {
							str[index][j++] = ' ';
						}
					}
					else {
						str[index][j++] = list[k];
						str[index][j++] = ' ';
					}
				}
			}

			index += 2;
			//cout << endl;
		}
		for (int i = 0; i < 10; i++) {
			if (i % 2 == 1) {
				for (int j = 0; j < 100; j++) {
					str[i][j] = ' ';
				}
			}
		}
		for (int i = 0; i < 10; i++) {
			if (i % 2 == 0) {
				for (int j = 0; j < 100; j++) {
					if (str[i][j] - '0' >= 0 && str[i][j] - '0' <= 9 && i < 2 * h - 2) {
						str[i + 1][j - 1] = '/';
						str[i + 1][j + 1] = '\\';
					}

				}
			}
		}
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 100; j++) {
				cout << str[i][j];
			}
			cout << endl;
		}
	}

	void DeepFirstSearch(node* root) {
		if (root == NULL) {
			return;
		}
		else {
			cout << root->info << ' ';
			DeepFirstSearch(root->left);
			DeepFirstSearch(root->right);
		}

	}

	void BreadthFirstSearch(node* root) {
		queue<node> myTree;
		if (root != nullptr) {
			myTree.push(*root);
		}
		while (!myTree.empty()) {
			cout << myTree.front().info << ' ';
			if (myTree.front().left != nullptr) {
				myTree.push(*(myTree.front().left));
			}
			if (myTree.front().right != nullptr) {
				myTree.push(*(myTree.front().right));
			}
			myTree.pop();
		}
	}

	//用于BFS递归的主函数
	void BFS_Recursion(node* root, int level, vector<vector<char>>& res) {
		if (root == nullptr) {
			return;
		}
		if (res.size() < level) {
			res.push_back(vector<char>());
		}
		res[level - 1].push_back(root->info);
		BFS_Recursion(root->left, level + 1, res);
		BFS_Recursion(root->right, level + 1, res);
	}

	void BreadthFirstSearch_recursion(node* root) {
		vector<vector<char>> res;
		BFS_Recursion(root, 1, res);
		for (int i = 0; i < res.size(); i++) {
			for (int j = 0; j < res[i].size(); j++) {
				cout << res[i][j] << " ";
			}
		}
	}

	//验证是否为二叉搜索树
	void isBST(node* root) {
		//先创建一个数组
		vector<char> midOrderArr;
		midOrder(root, midOrderArr);
		//输出看一下我的数组里面存的是不是中序遍历的值
		for (int i = 0; i < midOrderArr.size(); i++) {
			cout << midOrderArr[i] << ' ';
		}
		cout << endl;
		for (int i = 0; i < midOrderArr.size()-1; i++) {
			if (midOrderArr[i] >= midOrderArr[i + 1]) {
				cout << "该二叉树 不是一颗二叉搜索树！" << endl;
				return;
			}
		}
		cout << "该二叉树 是一颗二叉搜索树！" << endl;
	}

	//二叉树的中序遍历
	void midOrder(node* root,vector<char>& Arr) {
		if (root == nullptr) {
			return;
		}
		midOrder(root->left, Arr);
		Arr.push_back(root->info);
		midOrder(root->right, Arr);
	}

	bool isBST_Recursion(node* root,long long min,long long max) {
		if (root == nullptr) {
			return true;
		}
		if (root->info <= min || root->info >=max) {
			//cout << "该二叉树不是一个二叉搜索树";
			return false;
		}
		return isBST_Recursion(root->left, min, root->info) && isBST_Recursion(root->right, root->info, max);
	}

};

int main() {
    binaryTree T;
	node* root = T.getRoot();
	T.createTree(root);
	cout << "树的深度：" << T.depth(root) << endl;
	T.print(root);
	cout << "\n===========mid-order recursion===================="<<endl;
	T.isBST(root);
	cout << "\n===========upper and lower bounds recursion====================" << endl;
	if (T.isBST_Recursion(root, LONG_MIN, LONG_MAX)) {
		cout << "这是一颗二叉搜索树" << endl;
	}
	else {
		cout << "这不是一颗二叉搜索树" << endl;
	}
	/*cout << "\n===========DFS recursion====================" << endl;
	T.DeepFirstSearch(root);
	cout << "\n===========BFS QUEUE====================" << endl;
	T.BreadthFirstSearch(root);
	cout << "\n===========BFS recursion====================" << endl;
	T.BreadthFirstSearch_recursion(root);*/
	return 0;
}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

基于PHP高考志愿填报系统搭建私有化部署源码

基于PHP高考志愿填报系统搭建私有化部署源码

金秋志愿高考志愿填报系统是一款为高中毕业生提供志愿填报服务的在线平台。该系统旨在帮助学生更加科学、合理地选择自己的大学专业和学校&#xff0c;从而为未来的职业发展打下坚实的基础。 该系统的主要功能包括:报考信息查询、志愿填报数据指导、专业信息查询、院校信息查询…
阅读更多...
学习CSS3动画教程：手把手教你绘制跑跑卡丁车

学习CSS3动画教程：手把手教你绘制跑跑卡丁车

学习之前&#xff0c;请先听一段音乐&#xff1a;等登&#xff0c;等登&#xff0c;等登等登等登&#xff01;没错&#xff0c;这就是我们当年玩的跑跑卡丁车的背景音乐&#xff0c;虽然后来有了QQ飞车&#xff0c;但还是更喜欢跑跑卡丁车&#xff0c;从最初的基础板车&#xf…
阅读更多...
深入入IAEA底层LinkedList

深入入IAEA底层LinkedList

✅作者简介&#xff1a;大家好&#xff0c;我是再无B&#xff5e;U&#xff5e;G&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;再无B&#xff5e;U&#xff5e;G-CSDN博客 目标&#xff1a; 1.掌握LinkedList 2.…
阅读更多...
好用无广告的快捷回复软件

好用无广告的快捷回复软件

在现在的工作环境中&#xff0c;时间就是金钱。对于客服人员来说&#xff0c;能够快速而准确地回复客户的问题&#xff0c;是提高工作效率和客户满意度的关键。因此&#xff0c;一个实用的快捷回复工具是必不可少的。今天&#xff0c;我想向大家推荐一款好用且无广告的客服快捷…
阅读更多...
三勾软件 / 三勾点餐系统门店系统，java+springboot+vue3

三勾软件 / 三勾点餐系统门店系统，java+springboot+vue3

项目介绍 三勾点餐系统基于javaspringbootelement-plusuniapp打造的面向开发的小程序商城&#xff0c;方便二次开发或直接使用&#xff0c;可发布到多端&#xff0c;包括微信小程序、微信公众号、QQ小程序、支付宝小程序、字节跳动小程序、百度小程序、android端、ios端。 在…
阅读更多...
2024年受欢迎的主流待办事项提醒软件推荐

2024年受欢迎的主流待办事项提醒软件推荐

随着科技的飞速发展&#xff0c;2024年的今天&#xff0c;众多优秀软件如雨后春笋般涌现&#xff0c;极大地便利了我们的生活与工作。其中&#xff0c;待办事项提醒软件尤为受欢迎&#xff0c;它们不仅能记录日常待办任务&#xff0c;还能在关键时刻提醒我们及时处理&#xff0…
阅读更多...
1707jsp电影视频网站系统Myeclipse开发mysql数据库web结构java编程计算机网页项目

1707jsp电影视频网站系统Myeclipse开发mysql数据库web结构java编程计算机网页项目

一、源码特点 JSP 校园商城派送系统 是一套完善的web设计系统&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统采用web模式&#xff0c;系统主要采用B/S模式开发。开发环境为TOMCAT7.0,Myeclipse8.5开发&#xff0c;数…
阅读更多...
使用 SSH 连接 GitHub Action 服务器

使用 SSH 连接 GitHub Action 服务器

前言 Github Actions 是 GitHub 推出的持续集成 (Continuous integration&#xff0c;简称 CI) 服务它提供了整套虚拟服务器环境&#xff0c;基于它可以进行构建、测试、打包、部署项目&#xff0c;如果你的项目是开源项目&#xff0c;可以不限时使用服务器硬件规格&#xff1…
阅读更多...
（1）AB_PLC Studio 5000软件与固件版本升级

（1）AB_PLC Studio 5000软件与固件版本升级

AB_PLC Studio 5000软件与固件版本升级 1. 软件版本升级2. 固件版本升级1. 软件版本升级 使用将老程序从19版本升级到33版本。 step1：双击程序.ACD文件，打开界面如下。 step2：点击更改Controller，选择我们的新CPU的型号和版本号。点击确定 step3：点击确定，等待。 st…
阅读更多...
echart 多表联动value为null时 tooltip 显示问题

echart 多表联动value为null时 tooltip 显示问题

两个图表&#xff0c;第一个有tooltip,第二个隐藏掉 两个图表的 series 如下 // ----- chart1 ----series: [{name: Union Ads,type: line,stack: Total,data: [320, 282, 391, 334, null, null, null],},{name: Email,type: line,stack: Total,data: [220, 232, 221, 234, 29…
阅读更多...
[YOLOv8] 用YOLOv8实现指针式圆形仪表智能读数(三)

[YOLOv8] 用YOLOv8实现指针式圆形仪表智能读数(三)

最近研究了一个项目&#xff0c;利用python代码实现指针式圆形仪表的自动读数&#xff0c;并将读数结果进行输出&#xff0c;若需要完整数据集和源代码可以私信。 目录 &#x1f353;&#x1f353;1.yolov8实现圆盘形仪表智能读数 &#x1f64b;&#x1f64b;2.表盘智能读数…
阅读更多...
华普检测温湿度监测系统建设方案

华普检测温湿度监测系统建设方案

一、项目背景 随着医疗行业的蓬勃发展&#xff0c;药品、试剂和血液的储存安全直接关系到患者的健康。根据《药品存储管理规范》、《医疗器械冷链&#xff08;运输、贮存&#xff09;管理指南》、《疫苗储存和运输管理规范》和《血液存储要求》等相关法规&#xff0c;医院药剂…
阅读更多...
Satellite Communications Symposium(WCSP2022)

Satellite Communications Symposium(WCSP2022)

1.Power Allocation for NOMA-Assisted Integrated Satellite-Aerial-Terrestrial Networks with Practical Constraints(具有实际约束的 NOMA 辅助天地一体化网络的功率分配) 摘要&#xff1a;天地一体化网络和非正交多址接入被认为是下一代网络的关键组成部分&#xff0c;为…
阅读更多...
流畅的python-学习笔记_前言+第一部分

流畅的python-学习笔记_前言+第一部分

前言 标准库doctest 测试驱动开发&#xff1a;先写测试&#xff0c;推动开发 obj[key]实际调用实例的__getitem__方法 python数据模型 特殊方法 特殊方法一般自己定义&#xff0c;供py解释器调用&#xff0c;不推荐自己手动调用。 对于py内置类型&#xff0c;调用特殊方…
阅读更多...
八股文（C#篇）

八股文（C#篇）

C#中的数值类型 堆和栈 值类型的数据被保存在栈&#xff08;stack)上&#xff0c;而引用类型的数据被保存在堆&#xff08;heap&#xff09;上&#xff0c;当值类型作为参数传递给函数时&#xff0c;会将其复制到新的内存空间中&#xff0c;因此在函数中对该值类型的修改不会影…
阅读更多...
docker学习-docker常用其他命令整理

docker学习-docker常用其他命令整理

随便写写&#xff0c;后面有空再更新 镜像命令&#xff0c;容器命令已在之前略有更新&#xff0c;这次不写&#xff0c; 一、后台启动命令 # 命令 docker run -d 容器名 # 例子 docker run -d centos # 启动centos&#xff0c;使用后台方式启动 # 问题&#xff1a; 使用doc…
阅读更多...
JS-拖拽位移、放大缩小

JS-拖拽位移、放大缩小

对同一盒子拖拽位移、缩放&#xff0c;这其实是不符合js的逻辑的&#xff0c;位移和拖拽必然会互相影响&#xff0c;所以需要在布局上略加调整 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title…
阅读更多...
学习笔记：【QC】Android Q : telephony-phone 模块

学习笔记：【QC】Android Q : telephony-phone 模块

一、phone init 流程图 高清的流程图参考&#xff1a;【高清图&#xff0c;保存后可以放大看】 二、phone MO 流程图 高清的流程图参考&#xff1a;【高清图&#xff0c;保存后可以放大看】 三、phone MT 流程图 高清的流程图参考&#xff1a;【高清图&#xff0c;保存后可以…
阅读更多...
json返回工具类|世界协调时间（UTC）

json返回工具类|世界协调时间（UTC）

一、问题 世界协调时间&#xff08;UTC&#xff09;是一个标准的时间参考&#xff0c;通常被用于跨越不同时区的时间标准。要将 UTC 时间转换为中国时间&#xff08;中国标准时间&#xff09;&#xff0c;你需要将时间加上8个小时&#xff0c;因为中国位于 UTC8 时区。 初中知…
阅读更多...
智慧手术室手麻系统源码，C#手术麻醉临床信息系统源码，符合三级甲等医院评审要求

智慧手术室手麻系统源码，C#手术麻醉临床信息系统源码，符合三级甲等医院评审要求

手麻系统全套源码&#xff0c;C#手术麻醉系统源码&#xff0c;支持二次开发&#xff0c;授权后可商用。 手术麻醉临床信息系统功能符合三级甲等医院评审要求&#xff0c;实现与医院现有信息系统如HIS、LIS、PACS、EMR等系统全面对接&#xff0c;全面覆盖从患者入院&#xff0c;…
阅读更多...
最新文章

Copyright @ 2022~2023