图解LeetCode——98. 验证二叉搜索树

一、题目

给你一个二叉树的根节点 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^)/ ~ 「干货分享，每天更新」