图解LeetCode：验证二叉搜索树

一、题目

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/46475.html

节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/46475.html

二、示例

2.1> 示例 1：

【输入】root = [2,1,3]
【输出】true文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/46475.html

2.2> 示例 2：

【输入】root = [5,1,4,null,null,3,6]
【输出】false
【解释】根节点的值是 5 ，但是右子节点的值是 4 。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/46475.html

提示：

• 树中节点数目范围在 [1, 10^4] 内
• -2^31 <= Node.val <= 2^31 - 1

三、解题思路

根据题目描述，要去验证给定的二叉树是不是二叉搜索树。那么题目中给出了非常关键的一个信息就是——二叉搜索树，那么这种二叉树具有如下的特征：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/46475.html

【若它的左子树不空】则左子树上所有结点的值均小于它的根结点的值；
【若它的右子树不空】则右子树上所有结点的值均大于它的根结点的值；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/46475.html

针对这道题，我们其实可以通过中序遍历的方式进行解题。为什么是中序遍历呢？首先我们要先了解二叉树的遍历方式。我们以三个节点为例：node、leftNode和rightNode。遍历方式如下所示：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/46475.html

【前序遍历】node——>leftNode——>rightNode
【中序遍历】leftNode——>node——>rightNode
【后序遍历】leftNode——>rightNode——>node文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/46475.html

那么针对中序遍历，是先遍历左节点，然后是根节点，最后才是右节点；那么如果这个二叉树是二叉搜索树，遍历出来的每个节点的值的最终集合结果就是一个升序排列。所以，针对这个特性，我们就可以首先创建一个val变量，用于保存当前遍历的前一个节点值，然后每当遍历到一个节点node的时候，如果不满足node.val > val，则表示不是二叉搜索树了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/46475.html

以上就是本题的解题思路了，为了便于大家理解，我们以输入root = [5,1,4,null,null,3,6]为例，看一下具体的判断流程。请见下图所示：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/46475.html

四、代码实现

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;
 *     }
 * }
 */