题目
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:root = [2,1,3]
输出:true示例 2:
输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。
法一:前序遍历
class Solution {
public:
bool isValidBST(TreeNode* root,long left = LONG_MIN,long right = LONG_MAX) {
if(root == NULL) return true;
long x = root -> val; //根
bool isvalid_left = isValidBST(root->left,left,x); //左
bool isvalid_right = isValidBST(root -> right,x,right); //右
return left < x && x < right && isvalid_left && isvalid_right;
}
};
法二:中序遍历
class Solution {
public:
TreeNode*pre = NULL;
bool isValidBST(TreeNode* root) {
if(root == NULL) return true;
bool left = isValidBST(root -> left);
if(pre != NULL && pre -> val >= root -> val) return false;
pre = root;
bool right = isValidBST(root ->right);
return left && right;
}
};