图解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^)/ ~ 「干货分享,每天更新」
转载自:https://juejin.cn/post/7239540241932075045