题目描述
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左
子树
只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
出处
思路
按中序遍历,只要节点值是递增的即可,对于minNode需要特判。
代码
class Solution {
public:
bool valid(TreeNode* root,int& now,TreeNode* minNode) {
bool flag=true;
if(root->left)
flag=valid(root->left,now,minNode);
if(!flag) return false;
if(root->val>now||root==minNode)
now=root->val;
else return false;
if(root->right)
flag=valid(root->right,now,minNode);
return flag;
}
bool isValidBST(TreeNode* root) {
TreeNode* t=root;
while(t->left)t=t->left;
int min=t->val;
return valid(root,min,t);
}
};