• 【递归、搜索与回溯算法】第六节.98. 验证二叉搜索树和230. 二叉搜索树中第K小的元素


    作者简介:大家好,我是未央;

    博客首页:未央.303

    系列专栏:递归、搜索与回溯算法

    每日一句:人的一生,可以有所作为的时机只有一次,那就是现在!!!!!

    文章目录

    • 前言
    • 一、验证二叉搜索树
    •       1.1 题目描述
    •       1.2 题目解析
    •             1.2.1 算法原理
    •             1.2.2 代码编写
    • 二、二叉搜索树中第K小的元素
    •       2.1 题目描述
    •       2.2 题目解析
    •             2.2.1 算法原理
    •             2.2.2 代码编写
    • 总结


    前言


    一、验证二叉搜索树

    1.1 题目描述

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


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

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

    提示:

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

    示例1:


    示例2:


    1.2 题目解析

    1.2.2 算法原理

    本题我们可以采用递归的方法解决;

    而要写好一个递归,首先就要知道递归的三部曲:

    第一步:

    先找一下是否有和主问题相同的子问题!!!!!----->  关系到函数头的设计;


    第二步:

    只需要关心某一个子问题是如何解决即可!!!!-----> 关系到函数体的书写;


    第三步:

    最后再注意一下递归函数的出口即可;


    所以我们首先就要思考以上三个问题的解决:

    第一步:函数头

    我们题目要求

    而将两个链表合并就成了和主问题相同的子问题;

    而函数头就和题目中给定的函数头一样;


    第二步:函数体

    我们要找到某一个子问题如何解决;

    子问题即:

    要解决上述子问题:

    (1)

    (2)

    (3)


    第三步:递归出口

    递归出口即:


    1.2.1 代码编写


    二、二叉搜索树中第K小的元素

    2.1 题目描述

    描述:
    给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。


    提示:

    • 树中的节点数为 n 。
    • 1 <= k <= n <= 104
    • 0 <= Node.val <= 104

    示例1:


    示例2:


    2.2 题目解析

    2.2.1 算法原理

    本题我们可以采用递归的方法解决;

    而要写好一个递归,首先就要知道递归的三部曲:

    第一步:

    先找一下是否有和主问题相同的子问题!!!!!----->  关系到函数头的设计;


    第二步:

    只需要关心某一个子问题是如何解决即可!!!!-----> 关系到函数体的书写;


    第三步:

    最后再注意一下递归函数的出口即可;


    所以我们首先就要思考以上三个问题的解决:

    第一步:函数头

    我们题目要求

    而将两个链表合并就成了和主问题相同的子问题;

    而函数头就和题目中给定的函数头一样;


    第二步:函数体

    我们要找到某一个子问题如何解决;

    子问题即:

    要解决上述子问题:

    (1)

    (2)

    (3)


    第三步:递归出口

    递归出口即:


    2.2.2 代码编写


    总结

  • 相关阅读:
    62、使用python进行rk3588开发板进行推流亚马逊云服务上,进行实时播放
    矩阵相关操作与运算
    uniapp实现发送获取验证码
    微服务框架 SpringCloud微服务架构 21 RestClient 操作文档 21.5 批量导入文档
    Channel 是什么?
    2013年-2018年上市公司审计数据
    在宇宙的眼眸下,如何正确地关心东数西算?
    基于SkyEye运行Qt:著名应用程序开发框架
    关于出国留学和考研比较----以本人双非跨考计算机为例
    从CNN到Transformer:基于PyTorch的遥感影像、无人机影像的地物分类、目标检测、语义分割和点云分类
  • 原文地址:https://blog.csdn.net/qq_64861334/article/details/134033956