面试热点|二叉树那点事儿(一)上

简介: 前面写了很多篇工程相关的文章,今天准备写个数据结构和算法相关的文章。

0x00.前言和鸡汤


前面写了很多篇工程相关的文章,今天准备写个数据结构和算法相关的文章。


最近发现LeetCode的题目已经1500+了,记得去年夏天的时候信誓旦旦说每天刷一道一年也得几百道了,果然没过一星期这个flag就倒了,并且我看到了也没有扶起来...


说到底笔者还是个比较懒惰的人,毕竟人都是自然向下的,坐着不如倒着,舒适区虽然内心惭愧但是要想走出来还是很难的,也算是应了那句话:逃避虽可耻但很有用


但是总有那么一个时刻无法忍受自己,那就勇敢地走出去,别回头那种。


举个栗子:回看笔者从15年毕业到之后的4年时间,存款没有增长多少,体重增速倒是很给力,终于那个点来了,自己不愿意做个胖子,那就跑步吧!就这样从19年5月份开始,经历了1km到3km到5km到10km到21km的过程,累计跑了1100km,心肺功能变强体重变轻,状态也不一样了,再回头看看所谓的舒适区大概跟个狗窝差不多,所以无限风光在险峰 一点没错,疫情之前最近的一次LSD:


15.jpg

图:庆元旦业余自嗨跑20.19Km


笔者本硕都不是CS专业,相对来说数据结构和算法也一直都是短板,一直都是学了忘忘了学的怪圈,不过当我们发自肺腑地决定去改变这个短板的时候,我们也就离数据结构和算法强者不再遥远啦。


好了,鸡汤也喝完了,本文将从3道二叉树题目去尝试归纳一些共性问题,力争让我们快速获得解题切入点,开始吧!我们的征途是星辰大海!

16.jpg

图:爱天文也爱磕盐的师兄所拍猎户座M42星云


0x01.一道面试题


这也是笔者遇到的一线大厂出的一道比较基础的二叉树面试题,之前并没有做过,事后发现是leetcode的原题。


其实这个无所谓了,leetcode那么多题目,让我去编题目我也可以,所以这个是没有尽头的,从这些题目中提炼归纳上升到属于个人的心法和内力才是王道。


看下这个题目描述(leetcode103题):

给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

一图胜千言:


17.png

相信很多读者朋友都见过这道题目,没错 ,就是Z型变换遍历


1.1 思考一下


依稀记得笔者当时面对这个题目栈和队列弄了一堆,答得也不是很好,现在想一想是陷入细节了,这样下去容易把自己绕晕。


现在从更宏观的角度去看就是层次遍历的一个变种问题,在遍历的过程中记住当前的层索引编号来确定从左到右还是从右到左,但是这道题一直没有动手做,今天想起来了就做一下吧!


在做这道题之前,昨天晚上做了两道Easy级别二叉树的题目,在脉脉上有些大神说做easy的题目还不如练练字,只能说大神就是大神呀,比不了比不了,反正Easy的我也做的不少,如人饮水冷暖自知,起跑线不一样,各自努力吧


昨天做的两道题目分别是(笔者做的树的系列):

LeetCode100题:

给定两个二叉树,编写一个函数来检验它们是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

LeetCode101题:

给定一个二叉树,检查它是否是镜像对称的。


只有题目做多了,我们才能从中提炼归纳,我们都知道二叉树问题大部分都是可以用递归来解决的,代码简洁到蒙圈,像我这种不太灵光的,还是倾向于用迭代来实现,当然最后还是会递归想一想,逃避不懂的知识点是不明智的。


1.2 一个插曲:我和立体几何


笔者总是喜欢天马行空,因为凡事都是相通的


可能是因为空间思维能力弱(囧),所以有的事情总会让我记忆犹新。


高二开始学习立体几何,具体的细节虽然记不清了,但是每次遇到题目就想起老师说的各种技巧各种辅助线,最终磕磕绊绊也能做出来,当然也有一些是完全没有思路的,所以从那个时候起我喜欢解析几何胜于立体几何


考试之后老师会板书讲解,一听确实是那么回事,但是为啥当时就想不到呢?深深怀疑着自己的笨脑袋,但是也没办法,硬钢吧!


硬钢的路上并不轻松,即使做出来也花费很多时间,更多的是对此类问题的自信心逐渐减弱,这并不是个好现象,感受一下之前的题目:


18.png


19.png

没关系,请相信世界依然美好,上帝关上了窗的时候大概率给我们留着门呢。


果然让我找到了门,从我自己的角度去看,个人的解析计算能力是优于立体空间思维的,那为啥不能空间几何转换为数值计算呢?


原来有一种技术叫空间坐标系,这样就可以把空间几何的东西都坐标化,进而数值化,所以距离问题、面积问题、相交问题、平行问题等等都转换为了数值计算问题,深入学习了一段时间之后,自信心逐渐上来了,看到立体几何的题目不敢说庖丁解牛,最起码也看个大概,就这样立体几何再也没有成为我学习路上的拦路虎。


虽然这些事情已经过去很久了,但是解决立体几何问题的这种心理活动和现在做LeetCode上二叉树的问题很相似,一看题解貌似就是这么回事,一闭上题解,就不好下手(大囧)。


有时候,前进路上唯一的拦路虎,不是别人,就是我们自己,仅此而已。

            </div>
目录
相关文章
|
7月前
|
C++
二叉树进阶面试题(精华总结)【C++版本】
二叉树进阶面试题(精华总结)【C++版本】
|
7月前
力扣面试经典题之二叉树
力扣面试经典题之二叉树
50 0
|
3月前
|
算法
二叉树面试题
本文介绍了二叉树相关的几个经典算法问题。首先讲解了如何判断两棵树是否完全相同(LeetCode 100),并给出了代码示例。接着讨论了如何判断一棵树是否是另一棵树的子树(LeetCode 572),详细分析了子树的定义及判断方法。然后介绍了翻转二叉树(LeetCode 226)的实现方法,即在遍历时交换每个节点的左右子树。随后探讨了如何判断一棵树是否是对称的(LeetCode 101),通过对左右子树的递归比较来实现。最后分析了平衡二叉树的概念(LeetCode 110)及判断方法,并给出了优化后的代码示例。此外,还简要介绍了二叉树遍历及二叉树最近公共祖先(LeetCode 236)的问题
28 6
二叉树面试题
|
1月前
|
算法 Java
JAVA 二叉树面试题
JAVA 二叉树面试题
19 0
|
7月前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
7月前
【一刷《剑指Offer》】面试题 19:二叉树的镜像
【一刷《剑指Offer》】面试题 19:二叉树的镜像
|
7月前
【一刷《剑指Offer》】面试题 6:重建二叉树
【一刷《剑指Offer》】面试题 6:重建二叉树
|
7月前
|
算法 C++
数据结构和算法面试题:实现一个函数,将一棵二叉树转换为它的镜像。(递归或者非递归实现)
数据结构和算法面试题:实现一个函数,将一棵二叉树转换为它的镜像。(递归或者非递归实现)
42 0
|
7月前
|
算法 Java C++
数据结构与算法面试题:实现二叉树的遍历(前序、中序、后序、层序)。
数据结构与算法面试题:实现二叉树的遍历(前序、中序、后序、层序)。
44 0
|
7月前
数据结构之二叉树及面试题讲解(三)
数据结构之二叉树及面试题讲解(三)
47 0
下一篇
DataWorks