题目来源
本题来源为：
题目描述
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
算法原理
二叉搜索树大家都不陌生，这里还是在强调一下：
二叉树搜索树中序遍历的结果是一个有序序列
本题我将采取两种策略来解决此问题,并且我们借助全局变量来解决，发现全局变量的优势：
策略一：
根据二叉搜索树的定义，借助全局变量实现。
我们通过动图来模拟一下这个过程：
起先将全局变量初始化为无穷小，因为二叉搜索数的最小节点一定是比无穷小大的。
根据二叉搜索树中序遍历的结果是一个有序的序列的性质，我们采取中序的方式来更新我们的全局变量，所以每一次更新后的全局变量的值一定是要比之前的值大的，要是更新过程中比前面的值小，那么他就不符合二叉搜索树的性质，自然就不是一颗二叉搜索树。
策略一代码实现：
注意节点的取值范围最小为-231,因此定义变量初始化为long.
class Solution { long prev=LONG_MIN; public: bool isValidBST(TreeNode* root) { //空树直接返回true if(root==nullptr) return true; //左子树是不是符合 bool left=isValidBST(root->left); //判断当前层是否符合二叉搜素树 bool cur=false; if(root->val>prev) cur=true; //全局变量修改成当前位置的值 prev=root->val; //右 bool right=isValidBST(root->right); return left&&right&&cur; } };
策略二：
策略二是在策略一的基础上添加了剪枝。
使用剪枝可以加快我们的搜索过程，提高效率。
剪枝的过程很简单：
在我们dfs发现19节点已经不符合二叉搜索树的性质时，那么此时就不应在遍历30节点的右子树了，那么这一段我们就可以直接剪掉。
策略二代码实现
class Solution { long prev=LONG_MIN; public: bool isValidBST(TreeNode* root) { //空树直接返回true if(root==nullptr) return true; //左子树是不是符合 bool left=isValidBST(root->left); //左子树弄完发现不是二叉搜索树 //剪枝 if(left==false) return false; //判断当前层是不是二叉搜索树 bool cur=false; if(root->val>prev) cur=true; //剪枝 if(cur==false) return false; //全局变量修改成当前位置的值 prev=root->val; //右 bool right=isValidBST(root->right); return left&&right&&cur; } };
