(树)判断二叉树是否为BST
2024-10-21 03:41:27
- 题目:判断一颗二叉树是否为BST。
- 思路:其实这个问题可以有多个解决方法。
- 方法一:递归解决。根据BST的特性。左边的小于根节点的值,右边的大于根节点的值。并且对于每一棵子树都是如此。所以我们可以直接递归的对左右子树的值与根节点的值进行比较。左子树的值小于当前根节点的值,将当前根节点的值作为最大值传入左子树,左子树的值都小于他,递归处理;右子树的值都大于根节点的值,将根节点的值作为最小值传入右子树,右子树的值都大于他。
- 代码:
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode *root) {
return isValidBST(root, INT_MIN, INT_MAX);
}
bool isValidBST(TreeNode *root, int low, int high){
if (root == NULL )
return true;
if (low < root->val && root->val < high)
return (isValidBST(root->left, low, root->val) && isValidBST(root->right, root->val, high));
else
return false;
}
}; - 方法二:因为BST特性,所以我们可以利用遍历方法对他进行解决。对树进行中序遍历,将结果存储在vector中,如果容器中的值是递增排序的,那么它就是BST,否则就不是。
- 代码:
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode *root) {
vector<int> res;
isValidBST(root, res);
int len = res.size();
bool flag = true;
for (int i=; i<len-; i++){
if (res[i] >= res[i+]){
flag = false;
break;
}
}
return flag;
}
void isValidBST(TreeNode *root, vector<int> &res){
if (root == NULL)
return; isValidBST(root->left, res);
res.push_back(root->val);
isValidBST(root->right, res);
}
};
最新文章
- java-并发-线程
- .Net Webconfig连接字符串中数据库实例名带&#39;\&#39;的问题
- iOS底层基础知识-文件目录结构
- jQuery语法
- C++中的迭代器
- FUNCS.H中的函数声明
- C#读书笔记之并行任务
- WordPress主题制作教程1:文件构成
- Xcode5 编译ffmpeg,arm64版本;H264
- routes.IgnoreRoute(";{resource}.axd/{*pathInfo}";)作用
- iOS中json解析出现的null,nil,NSNumber的问题
- LInq 与lambda表达式
- UIColor,CGColor,CIColor三者间的区别和联系
- webpack4配置详解之常用插件分享
- [LeetCode] Kth Largest Element in a Stream 数据流中的第K大的元素
- [Kafka] [All about it]
- JS 正则表达式从地址中提取省市县
- centos 7 IP不能访问nginx Failed connect to 185.239.226.111:80; No route to host解决办法
- mysql test== 坑
- php 将秒数转换为时间(年、天、小时、分、秒)
热门文章
- docker+jenkins 部署持续集成环境
- UDP打洞原理及代码
- 试用 Eagle 9.1
- BZOJ4605:崂山白花蛇草水
- Zabbix配置微信报警通知
- 用反射封装HttpHandler,实现通过action方法名调用方法
- 侯捷STL学习(九)--关联式容器(Rb_tree,set,map)
- windows服务控制(开启/停止已有服务)
- When install ”matplotlib” with ”pip”, if you get the following error, it means the “freetype” and “png” libraries needed by matplotlib are not installed:
- oracle错误-ORA-12519, TNS:no appropriate service handler found