https://leetcode.com/problems/validate-binary-search-tree/
这道题是验证一个树是否为二叉搜索树,利用二叉搜索树的性质——二叉搜索树的中序遍历是顺序数组可以轻松的判断。但是,我们这里利用二叉树的定义进行递归的判断。需要注意的是递归判断的过程中,仅仅判断当前左右子结点和根节点的关系是不足以验证的。而要注意右子树的左孩子太小(小于根节点)或者左子树的右孩子太大(大于根节点)的这些情况,因此针对每一个节点,我们用区间来进行判断,代码如下:
class Solution {
public:
bool isValid(TreeNode* root, int* max, int* min){
if( root == nullptr )
return true;
if( min != nullptr && root->val <= *min )
return false;
if( max != nullptr && root->val >= *max )
return false;
return isValid( root->left , &root->val , min ) && isValid( root->right, max , &root->val );
}
bool isValidBST(TreeNode* root) {
return isValid( root, nullptr, nullptr);
}
};