面试经典150题 -- 二叉树搜索树 (总结)

总的链接 : 

https://leetcode.cn/studyplan/top-interview-150/

二叉搜索树相关概念 :

二叉搜索树是一个有序树

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  • 它的左、右子树也分别为二叉排序树;

如下图所示  : 两颗都是搜索树 

530 . 二叉搜索树的最小绝对差

. - 力扣(LeetCode)

本题与下题相同 : 

. - 力扣(LeetCode)

递归1

根据二叉搜索树的特点 ,左 < 根 < 右 , 使用中序遍历可以得到一个包含所有结点值得从小到大得有序数组 ;

然后遍历这个得到得数组 , 依次更新ans = min (ans , res[i] - res[i-1]) ;即可 ;

class Solution {
public:
    vector<int> res ;
    void dfs(TreeNode* root){
        if(root == nullptr) return ;
        dfs(root->left) ;
        res.push_back(root->val);
        dfs(root->right);
    }
    int getMinimumDifference(TreeNode* root) {
        int ans = INT_MAX ;
        dfs(root) ;
        for(int i=1;i<res.size();i++){
            ans = min(ans , res[i] - res[i-1]);
        }
        return ans ;
    }
};

递归2

其实在递归得过程中,可以借助一个pre结点表示当前结点得上一个结点,那么就不需要再创建一个数组来存了,直接在遍历得过程中,更新答案即可 ;

class Solution {
public:
    int ans = INT_MAX ;
    TreeNode* pre = nullptr ;
    void dfs(TreeNode* root){
        if(root == nullptr) return ;
        dfs(root->left) ;
        if(pre!=nullptr){
            ans = min(ans , root->val - pre->val);
        }
        pre = root ;
        dfs(root->right);
    }
    int getMinimumDifference(TreeNode* root) {
        dfs(root) ;
        return ans ;
    }
};

230 . 二叉搜索树中第k小的元素

递归(中序遍历)

用中序遍历得到一个排好序的存放所有节点值的数组,然后输出第k个元素即可 ;

class Solution {
public:
    vector<int> res ;
    void dfs(TreeNode* root){
        if(root == nullptr) return ;
        dfs(root->left) ;
        res.push_back(root->val);
        dfs(root->right);
    }
    int kthSmallest(TreeNode* root, int k) {
        dfs(root);
        return res[k-1] ;
    }
};

递归2 : 

找到第k个,直接返回即可,不用存数组 ;

class Solution {
public: 
    int t = 0 ;
    TreeNode* ans ;
    void dfs(TreeNode* root,int k){
        if(root == nullptr) return ;
        dfs(root->left,k) ;
        if(++t==k){
            ans = root ;
            return  ;
        }
        dfs(root->right,k);
    }
    int kthSmallest(TreeNode* root, int k) {
        dfs(root,k);
        return ans->val;
    }
};

98 . 验证二叉搜索树

用中序遍历得到结点值数组,判断该数组是否有序即可;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> vc;
    void traversal(TreeNode* root){
        if(!root) return;
        traversal(root->left);
        vc.push_back(root->val);
        traversal(root->right);
    }
    bool isValidBST(TreeNode* root) {
        vc.clear();
        traversal(root);
        for(int i=1;i<vc.size();i++){
            if(vc[i] <= vc[i-1]) return false;
        }
        return true;
    }
};

参考 : 

二叉树基础知识总结-CSDN博客

二叉树遍历总结 -- 基于LeetCode-CSDN博客

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/406450.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

PyTorch概述(六)---View

Tensor.view(*shape)-->Tensor 返回一个新的张量同之前的张量具有相同的数据&#xff0c;但是具有不同的形状&#xff1b;返回的张量同之前的张量共享相同的数据&#xff0c;必须具有相同数目的元素&#xff0c;可能具有不同的形状&#xff1b;对于经过view操作的张量&…

【Java程序设计】【C00286】基于Springboot的生鲜交易系统(有论文)

基于Springboot的生鲜交易系统&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于Springboot的生鲜交易系统 本系统分为系统功能模块、管理员功能模块、用户功能模块以及商家功能模块。 系统功能模块&#xff1a;在系统首页可以…

[HTML]Web前端开发技术28(HTML5、CSS3、JavaScript )JavaScript基础——喵喵画网页

希望你开心&#xff0c;希望你健康&#xff0c;希望你幸福&#xff0c;希望你点赞&#xff01; 最后的最后&#xff0c;关注喵&#xff0c;关注喵&#xff0c;关注喵&#xff0c;佬佬会看到更多有趣的博客哦&#xff01;&#xff01;&#xff01; 喵喵喵&#xff0c;你对我真的…

Linux-基础知识(黑马学习笔记)

硬件和软件 我们所熟知的计算机是由&#xff1a;硬件和软件组成。 硬件&#xff1a;计算机系统中电子&#xff0c;机械和光电元件等组成的各种物理装置的总称。 软件&#xff1a;是用户和计算机硬件之间的接口和桥梁&#xff0c;用户通过软件与计算机进行交流。 而操作系统…

【前端素材】推荐优质后台管理系统PORTAL平台模板(附源码)

一、需求分析 后台管理系统是一种具有多层次结构的软件系统&#xff0c;用于管理网站、应用程序或系统的后台操作和管理。下面是对后台管理系统的分层次、详细分析&#xff1a; 第一层&#xff1a;用户界面层 登录界面&#xff1a;提供用户登录验证&#xff0c;确保只有经过授…

村镇医院医疗中心污废水如何处理达标

污废水处理是村镇医院医疗中心运营中不可忽视的重要环节。如何有效处理污废水&#xff0c;使其达到相关标准&#xff0c;是保障医疗中心环境卫生的关键之一。 首先&#xff0c;村镇医院医疗中心应建立科学的废水处理系统。该系统应包括预处理、初级处理、中级处理和高级处理等环…

二十七、图像的均值模糊操作

项目功能实现&#xff1a;对一张图片进行均值模糊操作 按照之前的博文结构来&#xff0c;这里就不在赘述了 更多的图像模糊操作原理可参考博文&#xff1a;七、模糊操作&#xff0c;里面有详细原理讲解&#xff0c;只不过代码是python写的。 一、头文件 blurtest.h #pragma…

网络存储技术

第4章 存储文件系统 1.元数据 文件系统中的数据分为数据和元数据&#xff0c;数据是指普通文件中的实际数据&#xff0c;而元数据是描述数据属性的信息。 在Linux操作系统下&#xff0c;使用文件状态信息stat命令&#xff0c;可以显示文件的元数据如下。 [rootgitlab ~]# s…

英国客户亲临育菁,考察桌面级CNC机床

育菁桌面级CNC机床生产车间 2024年2月22日&#xff0c;英国某机床服务公司Alston和Gary一行拜访考察育菁&#xff0c;在育菁总经理Jimyang和总工程师Alan及海外营销中心总监Akuma的陪同下&#xff0c;参观了育菁桌面小型数控机床生产装配车间&#xff0c;并对育菁牌桌面型数控机…

《TCP/IP详解 卷一》第2章 Internet地址结构

目录 2.1 引言 2.2 表示IP地址 2.3 基本的IP地址结构 单播地址 全球单播地址&#xff1a; 组播地址 任播地址 2.4 CIDR和聚合 2.5 特殊用途地址 2.6 分配机构 2.7 单播地址分配 2.8 与IP地址相关的攻击 2.9 总结 2.1 引言 2.2 表示IP地址 IPv4地址&#xff1a;3…

【寸铁的刷题笔记】树、dfs、bfs、回溯、递归(二)

【寸铁的刷题笔记】树、dfs、bfs、回溯、递归(二) 大家好 我是寸铁&#x1f44a; 金三银四&#xff0c;树、dfs、bfs、回溯、递归是必考的知识点✨ 快跟着寸铁刷起来&#xff01;面试顺利上岸&#x1f44b; 喜欢的小伙伴可以点点关注 &#x1f49d; 上期回顾 感谢大家的支持&am…

Matlab/simulink基于vsg的风光储调频系统建模仿真(持续更新)

​ 1.Matlab/simulink基于vsg的风光储调频系统建模仿真&#xff08;持续更新&#xff09;

LeetCode 2583.二叉树中的第 K 大层和:层序遍历 + 排序

【LetMeFly】2583.二叉树中的第 K 大层和&#xff1a;层序遍历 排序 力扣题目链接&#xff1a;https://leetcode.cn/problems/kth-largest-sum-in-a-binary-tree/ 给你一棵二叉树的根节点 root 和一个正整数 k 。 树中的 层和 是指 同一层 上节点值的总和。 返回树中第 k …

sql注入 [极客大挑战 2019]FinalSQL1

打开题目 点击1到5号的结果 1号 2号 3号 4号 5号 这里直接令传入的id6 传入id1^1^1 逻辑符号|会被检测到&#xff0c;而&感觉成了注释符&#xff0c;&之后的内容都被替换掉了。 传入id1|1 直接盲注比较慢&#xff0c;还需要利用二分法来编写脚本 这里利用到大佬的脚…

学习使用在mysql中查询指定字段字符串包含多个字符串的方法

学习使用在mysql中查询指定字段字符串包含多个字符串的方法 使用LIKE关键字使用REGEXP关键字使用FIND_IN_SET函数使用INSTR函数和AND关键字 使用LIKE关键字 SELECT * FROM table_name WHERE column_name LIKE %string1% AND column_name LIKE %string2%;使用LIKE关键字&#x…

Python爬虫技术详解:从基础到高级应用,实战与应对反爬虫策略【第93篇—Python爬虫】

前言 随着互联网的快速发展&#xff0c;网络上的信息爆炸式增长&#xff0c;而爬虫技术成为了获取和处理大量数据的重要手段之一。在Python中&#xff0c;requests模块是一个强大而灵活的工具&#xff0c;用于发送HTTP请求&#xff0c;获取网页内容。本文将介绍requests模块的…

深入探究node搭建socket服务器

自从上篇中sokect实现了视频通话&#xff0c;但是是使用ws依赖库实现的服务端&#xff0c;所以最近再看ws源码&#xff0c;不看不知道&#xff0c;一看很惊讶。 接下来一点点记录一下&#xff0c;如何搭建一个简易的服务端socket&#xff0c;来实现上次的视频通讯。 搭建一个…

检索增强生成(RAG)——提示工程方法

在检索增强生成(RAG)过程中,提示工程也是一个不可忽略的部分。提示工程可以降低 RAG 应用出现的幻觉,提高 RAG 应用回答的质量。 下面简单介绍一些关于提示工程的论文。 欢迎关注公众号(NLP Research),及时查看最新内容 1. Thread of Thought(ThoT) 论文:Thread of …

LLM (Large language model)的指标参数

1. 背景介绍 我们训练大模型的时候&#xff0c;或者我们用RAG的时候&#xff0c;不知道我们的算法&#xff0c;或者我们的提示&#xff0c;或者我们的本地知识库是否已经整理得符合要求了。又或我们需要一个指标去评估我们目前的所有围绕大模型&#xff0c;向量数据库或外挂知…

【EI会议征稿通知】2024年软件自动化与程序分析国际学术会议(SAPA 2024)

2024年软件自动化与程序分析国际学术会议&#xff08;SAPA 2024) 2024 International Conference on Software Automation and Program Analysis 在当今科技社会中&#xff0c;软件产业呈快速发展趋势&#xff0c;软件自动化与程序分析技术在提高软件质量、降低开发成本、提升…