有什么做分销的几个网站,网站cmd做路由分析,深圳教育软件app开发,网络运维管理软件1. 题目
描述
给定一个二叉树根节点#xff0c;请你判断这棵树是不是二叉搜索树。
二叉搜索树满足每个节点的左子树上的所有节点的值均严格小于当前节点的值#xff1b;并且右子树上的所有节点的值均严格大于当前节点的值。
数据范围#xff1a;节点数量满足 1≤n≤10^4…1. 题目
描述
给定一个二叉树根节点请你判断这棵树是不是二叉搜索树。
二叉搜索树满足每个节点的左子树上的所有节点的值均严格小于当前节点的值并且右子树上的所有节点的值均严格大于当前节点的值。
数据范围节点数量满足 1≤n≤10^4^ 节点上的值满足 -2^31^ ≤val≤2^31^−1
示例1
输入
{1,2,3} 返回值
false
示例2
输入
{2,1,3} 返回值
true
2. 解题思路
先来看二叉搜索树的性质 二叉搜索树Binary Search Tree简称BST是一种特殊的二叉树其每个节点的值都大于其左子树中所有节点的值并且小于其右子树中所有节点的值。二叉搜索树允许快速查询、插入和删除操作多数操作插入、删除和查找的时间复杂度都是O(log n)。 以下是二叉搜索树的一些基本特性 1.左子树的所有节点的值都小于其父节点。 2.右子树的所有节点的值都大于其父节点。 3.左、右子树也必须是二叉搜索树。 4.每个节点只有一个父节点除了根节点和最多两个子节点左子节点和右子节点。 判断一颗二叉树是否为二叉搜索树依赖于树的左右子树。可以采用递归的方法。
先来看看是否满足递归的两个条件 可以看出判断二叉树是否为二叉搜索树的求解满足递归的两个条件因此可以采用递归的方法进行求解。
一颗二叉树是否为二叉搜索树依赖于节点的左右子树。对于左子树取值范围为-∞root.val]对于右子树取值范围为 [root.val,∞)。因此对应的递推公式如下 有了递推公式就可以很方便的写出对应的代码。
如果文字描述的不太清楚你可以参考视频的详细讲解。 Python版本https://www.bilibili.com/cheese/play/ep1372111https://www.bilibili.com/cheese/play/ep1372111 Java版本哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1367350 Golang版本数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1364775
3. 编码实现
/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param root TreeNode类* return bool布尔型*/
func isValidBST(root *TreeNode) bool {// write code herereturn recursion(root, math.MinInt32, math.MaxInt32) //对于二叉树来说取值范围为(-∞,∞)
}func recursion(root *TreeNode, min int, max int) bool {// 2. 递归终止条件:// 2.2 如果二叉树为空是搜索二叉树if root nil {return true}// 2.2 如果当前节点的值小于min或者 大于max则不是二叉搜索树if root.Val min || root.Val max {return false}// 1. 问题分解递推公式//左子树取值范围(min,root.val] 右子树取值范围[root.val,max)return recursion(root.Left, min, root.Val) recursion(root.Right, root.Val, max)
}
具体完整代码你可以参考下面视频的详细讲解。 Python版本https://www.bilibili.com/cheese/play/ep1372111https://www.bilibili.com/cheese/play/ep1372111 Java版本数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1367350 Golang版本https://www.bilibili.com/cheese/play/ep1364775https://www.bilibili.com/cheese/play/ep1364775
4.小结
判断一颗二叉树是否为二叉搜索树依赖于树的左右子树。可以采用递归的方法。对于节点的左子树取值范围为-∞root.val]对于节点的右子树取值范围为 [root.val,∞)。 《数据结构与算法》深度精讲课程正式上线啦七大核心算法模块全解析 ✅ 链表 ✅ 二叉树 ✅ 二分查找、排序 ✅ 堆、栈、队列 ✅ 回溯算法 ✅ 哈希算法 ✅ 动态规划
无论你是备战笔试面试、提升代码效率还是突破技术瓶颈这套课程都将为你构建扎实的算法思维底座。立即加入学习打卡与千名开发者共同进阶 Python编码实现https://www.bilibili.com/cheese/play/ss897667807https://www.bilibili.com/cheese/play/ss897667807 Java编码实现https://www.bilibili.com/cheese/play/ss161443488https://www.bilibili.com/cheese/play/ss161443488 Golang编码实现哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ss63997 对于二叉树的相关算法我们总结了一套【可视化图解】方法依据此方法来解决相关问题算法变得易于理解写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。 今日佳句长安回望绣成堆山顶千门次第开。
