二叉树刷题记(十-1.二叉树的镜像-2.二叉搜索树中的搜索)大家一起学习呗

简介: 二叉树刷题记(十-1.二叉树的镜像-2.二叉搜索树中的搜索)大家一起学习呗

前言

终于周五啦!忙碌的一周终于结束啦,小嘟现在终于能好好的写篇文章啦😆😆😆!

今天小嘟为读者带来了两道二叉树相关的题目,两道?我去,小嘟是不是疯啦!

嘿嘿嘿,今天这两道题可是很简单哦!,在力扣上都是简单级别的哦,小嘟原本想一天写一道,但是有点太简单,分开写难免有点水😂😂😂。so为了提高读者的阅读体验,小嘟决定将这两道题目放到一起,明天再接着做😭😭😭。

另外再叨叨一下下,读者觉得小嘟写的还不错的话,欢迎给小嘟👍点赞👉评论,谢谢啦!小嘟会好好干的。

话不多少,开搞!


正文

第一部分
1.1 题目

1.2 示例

1.3 题目分析
  • 1.3.1


小囔:小嘟,题目让我们干什么呢?

小嘟:嘿嘿嘿,你来啦,我看看,这个题目让我们在二叉搜索树中找一个结点,找到了返回以该结点为根的树,找不到,那么函数应该返回null。

1.3.2

小囔:好的,小嘟,这不好久没见你了,正好遇到个问题,这不来找你啦!

小嘟:原来是这,找我是来给你讲题,哼,生气。

1.3.3

小囔:我错了嘛,小嘟,其实找你是主要目的,讲题是顺带的喽,哈哈哈😂😂😂!

小嘟:这还差不多,你问吧!

1.3.4

小囔:小嘟,二叉树搜索树是个什么?没怎么听说过?

小嘟:这个之前讲过,小嘟在这里就在简单在说下,具体的可以查阅下方链接。二叉搜索树用一句话概括就是:一个结点的左子树的val都小于它,它的右子树的val都大于它(一个结点的val等于该结点的val,它在左子树还是右子树,这取决于我们代码怎么实现的)。

  • 1.3.5


小囔:嗯嗯,小嘟我基本明白了,我想到的思路是:我们可以先遍历二叉搜索树,如果当前结点与给定的值相等,那么我们就返回,小于我们就去左子树去找,大于我们就去右子树找,如果我们遍历完整个子树都没有找到,根据题意,那么我们应返回null。

小嘟:嗯嗯,小囔你真厉害,理解的可以啊,那你就写代码呗!

小囔:没问题,瞧好了您嘞!

1.4 代码及其结果展示
var searchBST = function(root, val) {
    while(root){
        if(val == root.val) return root;
        else if(val > root.val) root = root.right;
        else{ root = root.left;}
    }
    return null;
};


1.5 本题回顾
  • 本题我们用一个循环来遍历二叉搜索树,如果当前结点等于给定的值,那么返回以该结点为根的二叉搜索子树,不等的话就进行上述判断,代码非常简单,读者只要会遍历,就ok喽!
第二部分
2.1 题目

2.2 示例

2.3 题目分析


2.3.1

小囔:小嘟小嘟,还有这一道题目,看起来感觉有点难啊!

小嘟:别慌别慌,不要被题目吓着了,遇见题目要先冷静,好好分析一波,实在没有思路就看题解。

2.3.2

小囔:好的好的,小嘟,那我在看看。

小嘟:ok,加油!

小囔做题中...

2.3.3

小囔: 小嘟,我想出来了,我知道怎么做了。哈哈哈!

小嘟:你说说你是怎么做的呢?

小囔:分析这个示例,我们可以发现,左结点与右结点之间交换位置了,结点交换,他们下边的结点也会跟着交换。为了直观一点,也为了表达出题目"镜像"这个词,小囔就放一面镜子,如下所示:

画个图把小囔眼睛都累坏了创作不易,还请读者点赞支持呀!!!

2.4 代码及结果展示
var mirrorTree = function(root) {
    const mirro = (root01)=>{
        //key1处
        //判断是空树,或者是叶子结点,那么返回
        if(!root01||((!root01.left)&&(!root01.right)))
            return null;
        mirro(root01.left);//遍历左子树
        mirro(root01.right);//遍历右子树
        //交换左结点和右结点的中间值
        //也可以直接写成 let node 就行,不用是TreeNode()
        let node = new TreeNode();
        //有左结点和右结点
        if(root01.left &&root01.right){
            node = root01.left;
            root01.left = root01.right;
            root01.right = node;
        }
        //没有左结点
        else if(!root01.left){
           root01.left = root01.right;
           //key2处
           root01.right = null;
        }
        else{
        //没有右结点
            root01.right = root01.left;
            root01.left = null;
        } 
    }
    mirro(root);
    return root;
};
  • 这个是写 let node = new TreeNode()的结果

  • 这个是写let node 的结果
2.6 本题回顾(主要说下难点)

首先是上边的key1处,这个if第一点为了判断二叉树是不是空树,如果是空树,那就直接结束,函数返回root即可;还有另一点是为了我们遍历到叶子结点,我们就不必在递归进入函数进行相应的判断,就算判断结束,我们还是不进行任何操作(左右结点都为null)

其次是上边的key2处,我们交换结点之后,需要将之前的位置置为null(因为之前的右结点和左结点交换了,而左结点为null,所以这样写。)

结尾


读者们,大家好!本篇文章经过小嘟的2小时10分钟的努力,终于落下帷幕。

好累好累,在此感谢小囔的友情出演,谢谢。

希望本文对读者有所帮助。

不知道读者有没有和小嘟一样,一直坚持做题呢?

晚安各位,大家也都辛苦一周了!!!

若有问题,欢迎留言;觉得还有用的话,欢迎给小嘟👍点赞👉评论,谢谢啦!小嘟会持续输出哒,希望读者也能一直坚持下去。

溜啦溜啦...

相关文章
|
JavaScript
VUE element-ui之上传身份证照片正反面详细代码
VUE element-ui之上传身份证照片正反面详细代码
1646 0
VUE element-ui之上传身份证照片正反面详细代码
|
7月前
|
UED
销售易CRM:以用户体验为核心,驱动企业销售效能提升
销售易CRM是一款以用户体验为核心的企业客户关系管理工具。它通过简洁直观的操作界面降低学习成本,流畅稳定的系统性能提升办公效率,智能化功能助力精准识别高价值客户并优化销售流程,移动办公与离线支持打破时间和空间限制。全方位的高效、智能解决方案,助力企业在竞争中脱颖而出,实现持续发展。
|
10月前
|
设计模式 前端开发 调度
前端必须掌握的设计模式——工厂模式
工厂模式是一种创建型设计模式,通过工厂媒介提供统一接口来创建对象,客户端只需告知创建需求,具体逻辑由工厂处理。工厂模式分为简单工厂、标准工厂和抽象工厂,分别适用于不同场景下的对象创建需求。简单工厂利用静态方法创建对象,标准工厂通过具体工厂类减少耦合,抽象工厂则用于创建一系列相关或依赖对象的家族。
前端必须掌握的设计模式——工厂模式
|
Java 测试技术 Maven
maven 打包命令
maven 打包命令
159 6
|
小程序 IDE Serverless
【经验分享】支付宝小程序serverless云开发拓荒
【经验分享】支付宝小程序serverless云开发拓荒
313 6
|
人工智能 JSON Serverless
AI “黏土画风”轻松拿捏,手把手带你云端部署 ComfyUI
ComfyUI 是一款基于节点工作流稳定扩散算法的全新 WebUI,相对于传统的 WebUI,ComfyUI 的部署和学习曲线较陡峭,函数计算基于 Serverless 应用中心开发“ComfyUI 应用模版”,简化开发者的部署流程,帮助简单、快捷实现全新而精致的绘画体验,点击本文查看一键部署 ComfyUI 的方法。
19442 7
|
jenkins 持续交付 网络安全
Windows 2016 安装 Jenkins
Windows 2016 安装 Jenkins
83 0
|
设计模式 测试技术 Go
[设计模式 Go实现] 创建型~建造者模式
[设计模式 Go实现] 创建型~建造者模式
|
机器学习/深度学习 人工智能 Java
概率统计——重要术语及解释
概率统计——重要术语及解释
概率统计——重要术语及解释
|
Linux
LINUX上安装gstreamer,解决video.h找不到的错误
LINUX上安装gstreamer,解决video.h找不到的错误
444 0