image.png
如何判断一颗二叉树是二叉搜索树，基本的思路是用中序遍历的方法，因为二叉搜索树的中序遍历的结果是一个严格递增的数组，
比较简单的是直接保存出遍历的结果，然后看是否满足严格递增，这个时间复杂度是O(n), 空间复杂度O(n)
代码如下：
class Solution {
public:
bool isValidBST(TreeNode* root) {
vector<int> v;
traverse(root, v);
for (int i = 1; i < v.size(); i++) {
if (v[i] <= v[i - 1]) return false;
}
return true;
}
void traverse(TreeNode* root, vector<int>& v) {
if (!root) return;
traverse(root->left, v);
v.push_back(root->val);
traverse(root->right, v);
}
};
也可以用min max不断更新的值来避免O(n)的空间复杂度，解法2
class Solution {
public:
bool isValidBST(TreeNode* root) {
return isValidBST(root, NULL, NULL);
}
bool isValidBST(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
if(!root) return true;
if(minNode && root->val <= minNode->val || maxNode && root->val >= maxNode->val)
return false;
return isValidBST(root->left, minNode, root) && isValidBST(root->right, root, maxNode);
}
};
