C++递归实现验证⼆叉搜索树

这篇具有很好参考价值的文章主要介绍了C++递归实现验证⼆叉搜索树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

C++递归实现验证⼆叉搜索树

📟作者主页:慢热的陕西人

🌴专栏链接:力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言

题目链接

98. 验证二叉搜索树 - 力扣(LeetCode)

题目描述

给你⼀个⼆叉树的根节点root,判断其是否是⼀个有效的⼆叉搜索树。

有效⼆叉搜索树定义如下:

  • 节点的左⼦树只包含⼩于当前节点的数。
  • 节点的右⼦树只包含⼤于当前节点的数。
  • 所有左⼦树和右⼦树⾃⾝必须也是⼆叉搜索树。

解题思路

利用中序遍历;

后序遍历按照左⼦树、根节点、右⼦树的顺序遍历⼆叉树的所有节点,通常⽤于⼆叉搜索树相关题⽬。

算法思路:

如果⼀棵树是⼆叉搜索树,那么它的中序遍历的结果⼀定是⼀个严格递增的序列。

因此,我们可以初始化⼀个⽆穷⼩的全区变量,⽤来记录中序遍历过程中的前驱结点。那么就可以在
中序遍历的过程中,先判断是否和前驱结点构成递增序列,然后修改前驱结点为当前结点,传⼊下⼀
层的递归中。

算法流程:

  1. 初始化⼀个全局的变量**prev,⽤来记录中序遍历过程中的前驱结点的val**;

  2. 中序遍历的递归函数中

a.设置递归出⼝:root==nullptr的时候,返回true

b. 先递归判断左⼦树是否是⼆叉搜索树,⽤**retleft**标记;

c.然后判断当前结点是否满⾜⼆叉搜索树的性质,⽤**retcur**标记:

  • 如果当前结点的**val⼤于prev,说明满⾜条件,retcur改为true**;
  • 如果当前结点的val⼩于等于**prev,说明不满⾜条件,retcur改为false**;

d.最后递归判断右⼦树是否是⼆叉搜索树,⽤**retright**标记;

  1. 只有当**retleft、retcur和retright都是true的时候,才返回true**。

C++算法代码:

class Solution
{
long prev = LONG_MIN;
public:
bool isValidBST(TreeNode* root)
{
if(root == nullptr) return true;
bool left = isValidBST(root->left);
// 剪枝
if(left == false) return false;
bool cur = false;
if(root->val > prev)
cur = true;
// 剪枝
if(cur == false) return false;
prev = root->val;
bool right = isValidBST(root->right);
return left && right && cur;
}
};

总结

我们利用了剪枝的优化方式,提高了代码的运行效率,同时采用了全局变量prev来标记前序节点,也提高了程序的运行效率,并且将我们实现的过程简单化。文章来源地址https://www.toymoban.com/news/detail-734510.html

到了这里,关于C++递归实现验证⼆叉搜索树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣刷题19天

             这道题下面是前提:                                           如果没有这个前提,会出现下面情况(前序遍历会变成新的树):         运行代码:           下面代码中出现的问题:         和上面那道题逻辑一样。         运行代码:          

    2024年02月04日
    浏览(43)
  • 数据结构:力扣刷题

      给你一个  升序排列  的数组  nums  ,请你  原地  删除重复出现的元素,使每个元素  只出现一次  ,返回删除后数组的新长度。元素的  相对顺序  应该保持  一致  。然后返回  nums  中唯一元素的个数。 考虑  nums  的唯一元素的数量为  k  ,你需要做以下事情确

    2024年02月13日
    浏览(42)
  • 力扣刷题 - 数组篇

    https://leetcode.cn/problems/max-consecutive-ones/ 暴力解法: 定义一个变量来统计是否连续 https://leetcode.cn/problems/teemo-attacking/ 暴力解法: 记录每次中的开始时间与结束时间, 然后如果下一次中毒的是在结束时间之前, 就去更新开始时间(让它加上这个持续时间减去结束时间),如果是在之后

    2024年02月16日
    浏览(45)
  • 力扣刷题【第一期】

    1.爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 2.求两数的和(283) 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下

    2024年02月07日
    浏览(43)
  • 【力扣刷题 | 第十六题】

    目录 前言: 198. 打家劫舍 - 力扣(LeetCode) 213. 打家劫舍 II - 力扣(LeetCode)  总结: 我们今天继续刷动态规划的题,希望大家可以和我一起坚持下去。 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有

    2024年02月15日
    浏览(40)
  • 【力扣刷题 | 第十五天】

    目录 前言:  ​​​​​​​63. 不同路径 II - 力扣(LeetCode) 343. 整数拆分 - 力扣(LeetCode) 总结:         本篇我们主要刷动态规划的题,解题还是严格按照我们在【夜深人静写算法】栏目下的解题步骤,大家如果没学过动态规划的可以先看看我写的动态规划文章介绍。

    2024年02月15日
    浏览(42)
  • 【力扣刷题 | 第十七天】

    目录 前言: 55. 跳跃游戏 - 力扣(LeetCode) 45. 跳跃游戏 II - 力扣(LeetCode) 总结:         今天两道类型都是贪心算法,希望可以有所收获 给定一个非负整数数组  nums  ,你最初位于数组的  第一个下标  。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断

    2024年02月15日
    浏览(42)
  • 【力扣刷题 | 第十三天】

    今天随机进行练习,题型上不会有什么限制,主要还是练习STL算法。 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意:最终,合并

    2024年02月10日
    浏览(52)
  • 力扣刷题:删除重复元素

    当处理排序数组时,删除重复元素是一个常见的问题。首先,我们来看一下如何解决这个问题,然后再进一步讨论如何处理允许最多重复两次的情况。 问题描述:给定一个已排序的数组,删除重复的元素,使得每个元素只出现一次,并返回新的长度。 使用双指针方法。一个

    2024年02月13日
    浏览(49)
  • 力扣刷题笔记

    诸神缄默不语-个人CSDN博文目录 我以前刷过一波力扣,然后全忘了……从0开始的力扣复活赛! 以前刷题用的是Java,现在Java几乎忘光了,所以现在是Python 3 + Java双语选手。 以下题目按照力扣官方顺序排列。 449. 序列化和反序列化二叉搜索树 1281. 整数的各位积和之差 1749. 任意

    2024年02月14日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包