LeetCode初级算法之树:98 验证二叉搜索树

Stella981
• 阅读 788

01

题目信息

题目地址:
https://leetcode-cn.com/problems/validate-binary-search-tree/

给定一个二叉树,判断其是否是一个有效的二叉搜索树

假设一个二叉搜索树具有如下特征:

  • 节点的左子树只包含小于当前节点的数。

  • 节点的右子树只包含大于当前节点的数。

  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:     2    / \   1   3 输出: true

示例 2:

输入:     5    / \   1   4      / \     3   6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。      根节点的值为 5 ,但是其右子节点值为 4 。

02

解法一:递归

和上题一样可以很好的想到递归的思路,左边都是越来越小,右边是越来越大。这个地方容易产生一种错觉。

LeetCode初级算法之树:98 验证二叉搜索树

1

错误思路及代码:

就是只比较左右子节点的与父节点大小关系,如上图第一次是满足的,接下来递归左节点但他没有子节点结束并返回true,递归右节点也满足关系,继续递归其右节点因无子节点结束,左边同理。整个递归完成最终是true,但因为3比根节点5小应该在左子树不满足二叉搜索树

public boolean isValidBST(TreeNode root) {     if(root == null) return true;     if(root.left != null && root.left.val >= root.val)         return false;     if(root.right != null && root.right.val <= root.val)         return false;     return isValidBST(root.left) && isValidBST(root.right); }

那么问题就在于我们要比较的东西是什么?LeetCode初级算法之树:98 验证二叉搜索树 对于叶子节点2来说它比3小就可以没有限制,对于叶子节点6的位置它只能大于3并且小于5才有效 也就是说我们往左边走即是小那么就有一个上限之后不能超过,往右边走即是大就有一个下限。

LeetCode初级算法之树:98 验证二叉搜索树

3

按照整个过程如上图,从根节点开始往左进入递归,往左了以后这边的值都小于上限5并且3满足小于5继续递归找到2也是满足并且2之后的树上限是3,继续递归为空了出去,执行下一步的兄弟节点判断时超过了上线结束

代码如下:

public boolean isValidBST(TreeNode root) {     return process(root, null, null); } //递归方法 public boolean process(TreeNode node, Integer min, Integer max) {     if (node == null) return true;     if (min != null && node.val <= min) return false;     if (max != null && node.val >= max) return false;     if (!process(node.right, node.val, max)) return false;     if (!process(node.left, min, node.val)) return false;     return true; }

LeetCode初级算法之树:98 验证二叉搜索树

4

03

解法二:中序遍历

中序遍历是树的一种遍历方式,先数左子树在数中间在数右子树,那么通过中序遍历如果是真的二叉搜索树是一个从小到大的序列LeetCode初级算法之树:98 验证二叉搜索树 上图中序遍历:[2,3,6,5,3,6,7]

//记录前一个 Integer pre = null; public boolean isValidBST(TreeNode root) {     if (root == null) return true;     // 访问左子树     if (!isValidBST(root.left)) return false;     // 访问当前节点:如果当前节点小于等于中序遍历的前一个节点.即不满足     if (pre != null && root.val <= pre) return false;     pre = root.val;     // 访问右子树     return isValidBST(root.right); }

LeetCode初级算法之树:98 验证二叉搜索树

6

04

总结

其实两种解法也都是属于深度优先,一个在过程中处理遍历方式为后序,一个是中序。使用不同的遍历过程那么就需要想清楚在这种遍历下处理判断逻辑。

本文分享自微信公众号 - IT那个小笔记(qq1839646816)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
Wesley13 Wesley13
3年前
PTA 是否同一棵二叉搜索树(25 分)
是否同一棵二叉搜索树(25 分)给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2,1,3}和{2,3,1}插入初始为空的二叉搜索树,都得到一样的结果。于是对于输入的各种插入序列,你需要判断它们是否能生成一样的二叉搜索树。输入格式:输入包含若干组测
Kubrnete Kubrnete
4年前
二叉树题集(持续更新中)
对于二叉搜索树,我们规定任一结点的左子树仅包含严格小于该结点的键值,而其右子树包含大于或等于该结点的键值。1\.求二叉搜索树最大深度输入格式:输入给出一行整数序列作为二叉搜索树的键值,数字间以空格分隔,输入0结束(0不计入该二叉树键值)。输入样例:8685109110输出样例:4常规的求二叉搜索树深度的做法是递
Stella981 Stella981
3年前
LeetCode(98): 验证二叉搜索树
Medium!题目描述:给定一个二叉树,判断其是否是一个有效的二叉搜索树。一个二叉搜索树具有如下特征:节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例 1:输入:2/\
Stella981 Stella981
3年前
LeetCode(110):平衡二叉树
Easy!题目描述:给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树_每个节点_的左右两个子树的高度差的绝对值不超过1。示例1:给定二叉树 3,9,20,null,null,15,73/\920/
Stella981 Stella981
3年前
LeetCode112
非商业,LeetCode链接附上:https://leetcodecn.com/problems/pathsum/进入正题。题目:给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。说明: 叶子节点是指没有子节点的节点。示例:给定如下二叉树,以及目标和
Stella981 Stella981
3年前
LeetCode 230. 二叉搜索树中第K小的元素(Kth Smallest Element in a BST)
题目描述给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。说明:你可以假设k总是有效的,1≤k≤二叉搜索树元素个数。示例1:输入:root3,1,4,null,2,k13/\14
Wesley13 Wesley13
3年前
98. 验证二叉搜索树
题目描述给定一个二叉树,判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征:节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。输入:5/\14 /\ 
美凌格栋栋酱 美凌格栋栋酱
4个月前
Oracle 分组与拼接字符串同时使用
SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(
贾蔷 贾蔷
1星期前
力扣145题:二叉树的后序遍历, 解题思路与C++实现
题目介绍力扣第145题要求实现一个函数,该函数接收一个二叉树的根节点,并返回该树的后序遍历结果。后序遍历是一种遍历二叉树的算法,其顺序为:先遍历左子树,是右子树,是根节点。解题思路分析解题时,我们可以使用递归或迭代的方法。递归方法较为直观,但可能导致栈溢出
贾蔷 贾蔷
1星期前
力扣501题 解题思路和步骤 C++代码实现,力扣(leetcode)
问题背景及描述力扣501题要求我们找出在一个二叉搜索树(BST)中的众数。二叉搜索树是一种特殊的二叉树,其中每个节点的值都大于其左子树中的任何节点,且小于其右子树中的任何节点。众数是指在BST中出现次数最多的值。解题思路分析解题的关键在于理解BST的性质以