一、题目
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
二、示例
2.1> 示例 1：
【输入】root = [2,1,3]
【输出】true
2.2> 示例 2：
【输入】root = [5,1,4,null,null,3,6]
【输出】false
【解释】根节点的值是 5 ，但是右子节点的值是 4 。
提示：
- 树中节点数目范围在
[1, 10^4]内 -
-2^31<= Node.val <=2^31 - 1
三、解题思路
根据题目描述，要去验证给定的二叉树是不是二叉搜索树。那么题目中给出了非常关键的一个信息就是——二叉搜索树，那么这种二叉树具有如下的特征：
【若它的左子树不空】则
左子树上所有结点的值均小于它的根结点的值；
【若它的右子树不空】则右子树上所有结点的值均大于它的根结点的值；
针对这道题，我们其实可以通过中序遍历的方式进行解题。为什么是中序遍历呢？首先我们要先了解二叉树的遍历方式。我们以三个节点为例：node、leftNode和rightNode。遍历方式如下所示：
【前序遍历】
node——>leftNode——>rightNode
【中序遍历】leftNode——>node——>rightNode
【后序遍历】leftNode——>rightNode——>node
那么针对中序遍历，是先遍历左节点，然后是根节点，最后才是右节点；那么如果这个二叉树是二叉搜索树，遍历出来的每个节点的值的最终集合结果就是一个升序排列。所以，针对这个特性，我们就可以首先创建一个val变量，用于保存当前遍历的前一个节点值，然后每当遍历到一个节点node的时候，如果不满足node.val > val，则表示不是二叉搜索树了。
以上就是本题的解题思路了，为了便于大家理解，我们以输入root = [5,1,4,null,null,3,6]为例，看一下具体的判断流程。请见下图所示：
四、代码实现
class Solution {
public long val = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
if (!isValidBST(root.left)) return false;
if (val >= root.val) return false;
val = root.val;
return isValidBST(root.right);
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, Tre eNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
