文章目录

• 1.题目
• 2.示例
• 3.答案
• • ①中序遍历
  • ②递归

1.题目

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

提示：

• 树中节点数目范围在[1, 104] 内
• −231-2^{31}−231 <= Node.val <= 231−12^{31}- 1231−1

2.示例

输入：root = [2,1,3]
输出：true

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

3.答案

①中序遍历

在二叉搜索树中，左子树所有的值小于根，根的值小于右子树。而中序遍历的顺序是 左根右，可见二叉搜索树的中序遍历序列是一个有序序列。可以由此判断二叉搜索树是否有效。

   void inorder(TreeNode* root,vector &res){  //中序遍历if(!root) return ;inorder(root->left,res);res.push_back(root->val);inorder(root->right,res);}bool isValidBST(TreeNode* root) {vector res;inorder(root,res);for(int i=0;iif(res[i]>=res[i+1]) return false;  //如果不是有序序列}return true;}

②递归

左子树上所有的点小于根，右子树上所有的点大于根，，所以是每个结点的值都在一个区间内，而不是单纯地小于右孩子和大于左孩子。
根据要求 −231-2^{31}−231 <= Node.val <= 231−12^{31}- 1231−1，
而INT_MAX=231−12^{31}-1231−1,INT_MIN=−231-2^{31}−231 ，所以Int类型没办法将所有节点可能取值包含，如果节点取 INT_MAX,INT_MIN就无法正确判断。
所以最开始的区间范围是 [LONG_MIN,LONG_MAX], 对应的上下界 l,r 的类型也应该是long.

 // 递归检查，，bool qujian(TreeNode *root,long  l,long r){  //root子树应在的大小区间内if(!root) return true;// 当前结点在区间内if(l>=root->val||root->val>=r)   return false;  //根在区间内return qujian(root->left,l,root->val)&&qujian(root->right,root->val,r);  //左右子树均在区间内}bool isValidBST(TreeNode* root) {return qujian(root,LONG_MIN,LONG_MAX);}

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/validate-binary-search-tree