前言
终于周五啦!忙碌的一周终于结束啦,小嘟现在终于能好好的写篇文章啦😆😆😆!
今天小嘟为读者带来了两道二叉树相关的题目,两道?我去,小嘟是不是疯啦!
嘿嘿嘿,今天这两道题可是很简单哦!,在力扣上都是简单级别的哦,小嘟原本想一天写一道,但是有点太简单,分开写难免有点水😂😂😂。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分钟的努力,终于落下帷幕。
好累好累,在此感谢小囔的友情出演,谢谢。
希望本文对读者有所帮助。
不知道读者有没有和小嘟一样,一直坚持做题呢?
晚安各位,大家也都辛苦一周了!!!
若有问题,欢迎留言;觉得还有用的话,欢迎给小嘟👍点赞👉评论,谢谢啦!小嘟会持续输出哒,希望读者也能一直坚持下去。
溜啦溜啦...