思路一： 二叉搜索树中序遍历的结果是升序的， 把二叉树中序遍历一遍，看二叉树是否是升序的，如果不是的升序话那么该二叉树就不是二叉搜索树，否则就是二叉搜索树。
class Solution {
public:
vector<int>res;//储存中序遍历结果
bool isValidBST(TreeNode *root) {
if(root == nullptr)
return true;
traverse(root);//中序遍历
int len = res.size();
for(int i = 0; i < len - 1; i++){//检验数组是不是升序
if(res[i] >= res[i +1])
return false;
}
return true;
}
void traverse(TreeNode * root){//中序遍历
if(root){
traverse(root->left);
res.push_back (root -> val);
traverse(root -> right);
}
}
};
思路二：根据每个节点的值的上下限来判断。比如左孩子节点的值的上限就是小于根节点，右孩子的下限就是大于根节点的值
class Solution {
public:
bool isValidBST(TreeNode *root) {
if(root == nullptr)//测题的时候发现空树的答案是二叉搜索树的。。
return true;
return solve(root, INT_MIN, INT_MAX);
}
//low, high分别表示根节点的上下限。
bool solve(TreeNode * root, int low, int high){
if(root == nullptr)
return true;
//根节点的值域不符合要求
if(root -> val <= low || root -> val >= high)
return false;
//测试左孩子和右孩子
return solve(root -> left ,low, root->val) &&
solve(root -> right, root -> val, high);
}
};