二叉树刷题记(十-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分钟的努力,终于落下帷幕。

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

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

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

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

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

溜啦溜啦...

相关文章
代码随想录Day16 LeetCode T654 最大二叉树 T617 合并二叉树 T700 二叉搜索树中的搜索
代码随想录Day16 LeetCode T654 最大二叉树 T617 合并二叉树 T700 二叉搜索树中的搜索
49 0
|
6月前
|
算法
二叉树刷题记(六-二叉搜索树的第k大节点)
二叉树刷题记(六-二叉搜索树的第k大节点)
|
6月前
|
数据库 索引
【全网最易懂的红黑树讲解】一眼看懂二叉树、平衡树、红黑树,一文打尽
【全网最易懂的红黑树讲解】一眼看懂二叉树、平衡树、红黑树,一文打尽
|
Cloud Native
【刷题日记】450. 删除二叉搜索树中的节点
本次刷题日记的第 53 篇,力扣题为:450. 删除二叉搜索树中的节点,中等
|
6月前
leetcode700二叉搜索树中的搜索刷题打卡
leetcode700二叉搜索树中的搜索刷题打卡
43 1
|
算法
代码随想录算法训练营第十九天 | LeetCode 654. 最大二叉树、617. 合并二叉树、700. 二叉搜索树中的搜索、98. 验证二叉搜索树
代码随想录算法训练营第十九天 | LeetCode 654. 最大二叉树、617. 合并二叉树、700. 二叉搜索树中的搜索、98. 验证二叉搜索树
59 0
|
算法
代码随想录算法训练营第二十一天 | LeetCode 235. 二叉搜索树的最近公共祖先、701. 二叉搜索树中的插入操作、450. 删除二叉搜索树中的节点
代码随想录算法训练营第二十一天 | LeetCode 235. 二叉搜索树的最近公共祖先、701. 二叉搜索树中的插入操作、450. 删除二叉搜索树中的节点
63 0
|
算法
代码随想录算法训练营第十七天 | LeetCode 110. 平衡二叉树、257. 二叉树的所有路径、404. 左叶子之和
代码随想录算法训练营第十七天 | LeetCode 110. 平衡二叉树、257. 二叉树的所有路径、404. 左叶子之和
43 0
|
存储 C++
【C++杂货铺】一颗具有搜索功能的二叉树(下)
【C++杂货铺】一颗具有搜索功能的二叉树
40 0
|
存储 C++
【C++杂货铺】一颗具有搜索功能的二叉树(上)
【C++杂货铺】一颗具有搜索功能的二叉树
36 0