给定一个二叉树，判断它是否是合法的二叉查找树(BST)
一棵BST定义为：
- 节点的左子树中的值要严格小于该节点的值。
- 节点的右子树中的值要严格大于该节点的值。
- 左右子树也必须是二叉查找树。
- 一个节点的树也是二叉查找树。
您在真实的面试中是否遇到过这个题？
Yes
样例
一个例子：
2
/ \
1 4
/ \
3 5
上述这棵二叉树序列化为 {2,1,4,#,#,3,5}.
思路：
最初解法（错误解法）：
使用递归的方式，按照二叉搜索树的定义去判断。考虑各种情况，然后递归。但是这种方法，一开始有漏洞，只能通过87%。
发现问题所在：像是{10,5,15,#,#,6,20}这种实例不能通过，经过考虑，确实存在问题。
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: True if the binary tree is BST, or false
*/ /*
思路：使用递归的方式，按照二叉搜索树的定义去判断。考虑各种情况，然后递归。
但是这种方法，一开始有漏洞，只能通过87%。
发现问题所在：像是{10,5,15,#,#,6,20}这种实例不能通过，经过考虑，确实存在问题。 */
bool isValidBST(TreeNode *root) {
// write your code here if(root==NULL){
return true;
} if(root->left==NULL&&root->right==NULL){
return true;
} if(root->left!=NULL&&root->right==NULL){
if(root->left->val<root->val){
return isValidBST(root->left);
}
else{
return false;
}
} if(root->right!=NULL&&root->left==NULL){
if(root->right->val>root->val){
return isValidBST(root->right);
}
else{
return false;
}
} if(root->left!=NULL&&root->right!=NULL){
if(root->val<root->right->val&&root->val>root->left->val){
return isValidBST(root->left)&&isValidBST(root->right);
}
else{
return false;
}
}
}
};
解决方法1：借助辅助空间，因为中序遍历一定是有序的。
/
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode left, right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/
* @param root: The root of binary tree.
* @return: True if the binary tree is BST, or false
*/ /*
解决方法1：借助辅助空间，因为中序遍历一定是有序的。
*/
void help(vector<int> &vec,TreeNode *root){
//使用中序遍历，将元素压入容器；
if(root==NULL)
return ;
help(vec,root->left);
vec.push_back(root->val);
help(vec,root->right);
}
bool isValidBST(TreeNode *root) {
if(root==NULL)
return true;
vector<int> vec;
help(vec,root); int last=vec[0];
vec.erase(vec.begin());
for(auto e:vec){
if(last>=e)
return false;
last=e;
}
return true;
}
解决方法2：prev指针记录前一个节点，省下了辅助空间，而且要注意prev传进去还应该是引用。方法很好！
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: True if the binary tree is BST, or false
*/ /* 解决方法2：prev指针记录前一个节点，省下了辅助空间，而且要注意prev传进去还应该是引用。 */ bool isValidBST(TreeNode* root)
{
TreeNode *pre = NULL;
return validate(root, pre);
} bool validate(TreeNode *root, TreeNode *&pre)
{
if (root == NULL)
return true;
if (!validate(root->left, pre))
return false;
if (pre != NULL && pre->val >= root->val)// 如果当前还是NULL那就先不管吧，继续往下运行。
return false;
pre = root;
return validate(root->right, pre);
}
};