likes
comments
collection
share

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

作者站长头像
站长
· 阅读数 34

一、题目

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下:

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

二、示例

2.1> 示例 1:

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

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

2.2> 示例 2:

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

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

提示:

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

三、解题思路

根据题目描述,要去验证给定的二叉树是不是二叉搜索树。那么题目中给出了非常关键的一个信息就是——二叉搜索树,那么这种二叉树具有如下的特征:

若它的左子树不空】则左子树上所有结点的值均小于它的根结点的值; 【若它的右子树不空】则右子树上所有结点的值均大于它的根结点的值;

针对这道题,我们其实可以通过中序遍历的方式进行解题。为什么是中序遍历呢?首先我们要先了解二叉树的遍历方式。我们以三个节点为例:nodeleftNoderightNode。遍历方式如下所示:

前序遍历node——>leftNode——>rightNode中序遍历leftNode——>node——>rightNode后序遍历leftNode——>rightNode——>node

那么针对中序遍历,是先遍历左节点,然后是根节点,最后才是右节点;那么如果这个二叉树是二叉搜索树,遍历出来的每个节点的值的最终集合结果就是一个升序排列。所以,针对这个特性,我们就可以首先创建一个val变量,用于保存当前遍历的前一个节点值,然后每当遍历到一个节点node的时候,如果不满足node.val > val,则表示不是二叉搜索树了

以上就是本题的解题思路了,为了便于大家理解,我们以输入root = [5,1,4,null,null,3,6]为例,看一下具体的判断流程。请见下图所示:

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

四、代码实现

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

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

今天的文章内容就这些了:

写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享

更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」

转载自:https://juejin.cn/post/7239540241932075045
评论
请登录