检查是否是BST 牛客网 程序员面试金典 C++ java Python
2024-08-31 06:42:57
检查是否是BST 牛客网 程序员面试金典 C++ java Python
- 题目描述
- 请实现一个函数,检查一棵二叉树是否为二叉查找树。
- 给定树的根结点指针TreeNode* root,请返回一个bool,代表该树是否为二叉查找树。
C++
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Checker {
public:
//run:4ms memory:472k
bool checkBST(TreeNode* root) {
if (NULL == root) return true;
if (NULL != root->left){
if (root->left->val > root->val) return false;
if (root->left->right && (root->left->right->val > root->val)) return false;
}
if (NULL != root->right){
if (root->right->val < root->val) return false;
if (root->right->left && (root->right->left->val < root->val)) return false;
}
return checkBST(root->left) && checkBST(root->right);
}
};
java
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class Checker {
// run: 42ms memory:10128k
public boolean checkBST(TreeNode root){
if (null == root) return true;
if (root.left != null){
if (root.left.val > root.val) return false;
if (root.left.right !=null && root.left.right.val > root.val) return false;
}
if (root.right != null){
if(root.right.val < root.val) return false;
if(root.right.left != null && root.right.left.val < root.val) return false;
}
return checkBST(root.left) && checkBST(root.right);
}
}
Python
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Checker:
#run:48ms memory:5852k
def checkBST(self, root):
if None == root: return True
if None != root.left:
if root.left.val > root.val: return False
if None != root.left.right and root.left.right.val > root.val: return False
if None != root.right:
if root.right.val <root.val: return False
if None != root.right.left and root.right.left.val < root.val: return False
return self.checkBST(root.left) and self.checkBST(root.right)
最新文章
- 创建WP8试用应用
- bzoj2083【Poi2010】Intelligence test
- ThinkPHP3.2.3使用cli命令行模式
- java设计模式之-----桥接模式
- javascript设计模式学习之五——策略模式
- 从代码都发布遇到的问题总结(C#调用非托管dll文件,部署项目) 转
- Method ";setAge"; failed for object action.RegistAction@1f05562b [java.lang.No....
- js 判断通过什么打开(安卓、苹果、微信、QQ、浏览器、某个app应用…)
- Flex/AS3 base64指定字符编码
- margin 和 padding 的本质区别
- EM算法(Expectation Maximization)
- vue页面引入外部js文件遇到的问题
- 【翻译】Neural Collaborative Filtering--神经协同过滤
- GoldenGate抽取Informix数据库安装及配置
- 搭建git 服务器
- IBM MQ常用命令
- Spring boot ---- java.lang.NoClassDefFoundError: javax/servlet/ServletContext
- hdoj 5199 Gunner map
- 【BZOJ1787】[Ahoi2008]Meet 紧急集合 LCA
- 使用vue的v-model自定义 checkbox组件
热门文章
- PHP中的PDO操作学习(二)预处理语句及事务
- mysql5.7当两个字段名类似,查询时会出错
- 织梦 arclist调用副栏目内容解决办法
- LR虚拟用户已设置集合点,但controller无法设置集合点策略的解决方案
- python3.7发送邮件带附件
- 鸿蒙内核源码分析(文件系统篇) | 用图书管理说文件系统 | 百篇博客分析OpenHarmony源码 | v63.01
- vue成就购物城的功能 (展示增删改查)
- A Three-Stage Self-Training Framework for Semi-Supervised Semantic Segmentation
- 简单介绍session,cookie,token以及区别
- Docker小白到实战之Docker Compose在手,一键足矣