粉丝1.6万获赞9.2万


如果一颗二叉数有十个度为二的节点,五个度为一的节点,则度为零的节点个数是多少个呢? a 九个 b 十一个 c 十五个 d 不确定。 那么首先呢,我们来公布答案,答案是 b 十一个。解决这个问题呢,首先我们要清楚数解点度的概念与二差数的性质, 数节点的度数就是为该节点子数或分支的个数。比方说一号节点有三个孩子, 分别是二、三、四,那么一号节点的度数是三,二号节点的孩子是五和六,他的度数是二。 二差数当中任意节点的度数都小于等于二。比方说二差数替当中有两个度是二的节点,一个度是一的节点,三个度是零的节点。 现在我们回到问题,假设一个二叉数有 a 个度为二的节点, b 个度为一的节点, c 个夜节点。 那么由于每出现一个度为二的节点,就会增加两条指向孩子节点的边,每出现一个度为一的节点,就会增加一条指向孩子的边。 夜节点没有边,只像孩子,所以这个二叉数的边的总数量就是二, a 加 b。 另一个方面看呢,由于总共有 a 加 b 加 c 个节点,除根节点外,每个节点都有一条向上的边与他的负节点相连,所以边的数量等于 a 加 b 加 c 减一。 那么我们得到等式二, a 加 b 等于 a 加 b 加 c 减一,所以 a 等于 c 减一, 也就是度为零的夜节点个数是度为二的节点,个数加一。在题目当中告诉我们了,有一棵二叉树 有十个度为二的节点,所以度为零的节点个数是十加一等于十一,所以选 b, 那么小伙伴们你们答对了吗? 最后啊,我们留一个课后练习,有十个页节点的二岔数中有多少个度为二的节点呢? 好的,那么今天的内容我们就分享到这,喜欢动画奖编程的小伙伴一定不要忘了点赞、收藏、投币加关注哦! 好的,我们下期再会,拜拜。

今天来讲二叉术的几种便利方式,最常用的二叉术便利方式有前序便利、中需便利以及后续便利,还有不太常用的层次便利。 我们首先来看一个最简单的二差数,其中 av 跟结点 d 和 c 分别是左子结点和右子结点, 也可以称为左子数和右子数。而今天要讲的前序、中序、后续便利是针对于根结点来说的。我们来看这个最简单的二叉数的前序、 中序、后序以及层次便利的结果分别是什么?首先来看前序,前序便利是指便利的第一个结点为根结点,然后是左子结点,最后是右子结点,前序便利的顺序可以记作为 左右,所以这个最简单的二差数的前序便利结果为 abc。 然后我们再来 看中序便利,中序便利是指根结点在左右子结点中间,首先是左子结点,然后是根结点,最后是右子结点,中序便利的顺序可以记作为左跟右,所以这个二叉数的中序便利结果为 dac。 然后是后续便利。后续便利是指根结点在左右子结点之后,首先是左子结点,然后是右子结点,最后是根结点,后续便利的顺序可以寄作为左右跟,所以这个二差数的后续便利结果为 bca。 当然考试题目不会这么简单,我们来看一个稍微复杂一点的二差数,你可以根据刚才所讲的内容分别写出这个二差数的前序、中序以及后续便利的结果吗?那我们一起来看一下这个二差数的三种便利 结果分别是什么?首先来看前序便利,前序便利的顺序为跟左右,那我们来看这颗二叉数,首先第一个跟是 a, 然后找到左子数 b, 你会发现 b 也是 d 和 e 的跟,所以第二个是 b, 再找 b 的左子数 d, e 也同样是 f 的根结点,所以第三个为 d, 然后再找 d 的左右子数,根据跟左右的顺序,没有左子数就直接写右子数,所以第四个为 f。 到这儿你会发现 b 的左子数部分已经便利完了,然后是节点 b 的右子数, 所以第五个是 e, 现在跟节点 a 的左子数部分已经全部便利完了,所以下一个是节点 c, c 没有左子数,所以下一个是节点 g, 然后是 g 的左子数,所以最后一个为 h, 所以这个 二叉数的前序便利结果为 abdfecgh, 你做对了吗?还有一种方法,首先根据根左右的顺序写出 abc, 然后来看节点 b, b 的后面应该是 b 的左右子数,所以 b 的后面应该是 d 和 e。 再来看节点 d, d 的后面也应该是 d 的左右子数,不过 d 没有左子数,所以直接写右子数的 f。 然后来看节点 c, c 的后面应该是 c 的左右子数,没有左子数,所以直接写右子数 g, g 的后面为 g 的左右子数,所以写 h。 你觉得哪种方法更方便呢? 然后再来看这个二叉数的中序便利中序便利的顺序是左跟右,所以先来看跟解表 a 的左子数, a 的左子 节点为 b, 但是 b 也是 b 和一的根节点,所以再来找 b 的左子节点 b, b 只有右子数,所以先写 b, 根据左跟右的顺序,然后是节点 f, 然后节点 b 的左子数部分就便利完成了, 所以第三个应该是 b, 然后是 b 的柚子结点 e。 现在根结点 a 的左子数部分已经便利完了,所以根据左跟右的顺序,下个应该是根结点 a, 然后是 a 的柚子数部分。 a 的柚子结点 c 没有左子数,所以第六位应该是 c, 然后是结点 c 的柚子结点 g。 因为 g 有左子数,所以应该先写 h, 最后是 g, 所以这个二叉数的中序便利结果为, t f b e a c h g。 然后我们用另外一种方式来试一下, 先根据左跟右的顺序写出 bsc, 然后来看节点 b, 节点 b 的前面应该是 d, 后面应该是 e, 然后来看节点 d。 节点 b 的前面应该是他的左子数, 但是他没有左子数,所以前面不写任何节点。然后 d 的后面应该是他的柚子节点 f, 然后来看节点 c, c 的前面应该是他的左子数,但他没有左子节点,所以 c 的前面不写。 然后 c 的后面应该是他的柚子树,所以他的后面应该写节点制。再看枝节点,枝节点的前面是他的左子树 h, 后面是他的柚子树。因为没有柚子树,所以为空 到这儿,所有的节点都便利完了。你觉得这两个方法哪个更简单呢?然后是他的后续便利,后续便利的 顺序是左右跟,所以先来看跟结点的左子结点臂。因为结点臂也是 d 和 e 的根,所以来看 b 的左子竖 d, b 没有左子竖,所以先写他的右子竖 f, 然后写 f 的跟结点臂。结点 d 是结点臂的左子竖, 所以下一个应该写节点 b 的柚子数 e, 然后写节点 b 和 e 的跟节点 b, 节点 b 是根节点 a 的左子数, 所以下一个应该写节点 a 的柚子树 c, 但是节点 c 也有字节点,所以应该写节点 g, 但节点之也有字节点,所以应该先写 g 的字节点 h, 然后写 h 的根结点制,然后写结点制的根结点 c, 最后写根结点 a, 所以这个二叉数的后续便利结果为 fdebhgca。 你可以用另外一种方法写出这个二叉数的后续便利结果吗?可以暂停试一下哦。我们来用另外一种方法写出他的后续便利结果,所以应该按照左右跟的顺序先写出 bca, 然后来看节点 b, 节点 b 的前面应该是他的左右指数,所以应该是 d 和 e, 再来看节点 d, 他的前面应该是 f, 然后来看节点 c, c 的前面应该是节点 g, g 的前面应该是节点 h, 所以你做对了吗? 层次便利则是将二叉数的节点按照从左到右,从上到下的顺序进行排列的,所以这个二叉数的层次便利的结果为 abcdegfh。 你学会了吗?点个赞吧!

![[算法学习Day457]二叉树的最近公共祖先 需求分析:
题目要求在一棵二叉树中,找到两个节点 p 和 q 的最近公共祖先 (Lowest Common Ancestor, LCA)。二叉树是标准的二叉树结构,每个节点包含一个值 val 和指向左右子节点的指针 left 和 right。我们需要设计一个高效的算法来找到这两个节点的最近公共祖先。
算法选型:
这个问题可以通过递归深度优先搜索 (DFS) 来解决。具体思想是从根节点出发,递归遍历左右子树。如果某个节点是 p 或 q,则返回该节点。如果在左子树和右子树分别找到了 p 和 q,那么当前节点就是它们的最近公共祖先。否则,返回子树中非空的部分(即找到的 p 或 q)。
逻辑实现:
首先,判断当前节点是否为空,或者当前节点是否是 p 或 q,如果是,则返回当前节点。
然后,递归地查找左子树和右子树中的最近公共祖先。
如果左子树返回 null,则说明 p 和 q 都不在左子树中,返回右子树的结果。如果右子树返回 null,同理,返回左子树的结果。
如果左右子树都返回非空值,说明 p 和 q 分别位于当前节点的左右子树上,当前节点就是它们的最近公共祖先。
#计算机 #面试 #秋招 #算法 #Java](https://p3-pc-sign.douyinpic.com/image-cut-tos-priv/320346e1e63579b2ed74567ca8c9b145~tplv-dy-resize-origshort-autoq-75:330.jpeg?lk3s=138a59ce&x-expires=2110485600&x-signature=KrR4FSuvM%2Bqy14U%2B4U5QW2yyufU%3D&from=327834062&s=PackSourceEnum_AWEME_DETAIL&se=false&sc=cover&biz_tag=pcweb_cover&l=2026112006335255E794ADB86A74C80D63)

![[算法学习Day499]翻转二叉树 需求分析:
该问题要求反转一个二叉树,即将树中的每个节点的左右子树交换位置。输入是二叉树的根节点,输出是该二叉树的根节点,且该二叉树已经被反转。
算法选型:
该问题使用了深度优先搜索(DFS)算法来遍历树。深度优先搜索通常用于二叉树的遍历和处理,特别适合树结构的修改操作。DFS可以通过递归实现,逐层访问每个节点,并在每个节点处交换其左右子树。
逻辑实现:
递归实现:从根节点开始,首先检查当前节点是否为空。如果为空,直接返回,因为没有节点需要处理。
对当前节点,交换其左右子节点。
对交换后的左右子树递归执行相同的操作,直到整个树被反转。
最终返回根节点,该节点指向的树已经完成了反转。
#计算机 #面试 #秋招 #算法 #Java](https://p3-pc-sign.douyinpic.com/image-cut-tos-priv/55d2681bb427b5716ee718effcb5b815~tplv-dy-resize-origshort-autoq-75:330.jpeg?lk3s=138a59ce&x-expires=2110485600&x-signature=XuXf3BAs%2FnWXbdbQ6yD2NS%2FvfJ4%3D&from=327834062&s=PackSourceEnum_AWEME_DETAIL&se=false&sc=cover&biz_tag=pcweb_cover&l=2026112006335255E794ADB86A74C80D63)

大家好,这里是同龄学院的算法公开课堂,我是韩非。上节课呢,我们讲了这个二差数便利的四种顺序,前序,中序,后续以及程序便利。那么呢还介绍了三种便利的算法,地规迭代以及 mores 便利。 这节课呢,我们就来讲这个地规便利怎么样呢?使用这个地规便利来实现上面这四种顺序的一个便利啊。那么这里呢,我们来先画一个简图啊, 这个阿扎树,我们呢先在这里画一个最简单的这个阿扎树的一个结构啊,一个副结点,两个子结点。我们先呢通过这个地规啊,先来看这个前序便利,前序便利,我们首先呢,这里是一个入的结点, 那么作为我们函数的这个入餐啊,入的,作为这个入餐,肯定知道这个入的节点呢,是我们呃第一个拿到的节点, 那么第一个拿到的节点我们要不要打印呢?按照这个前序便利的这个顺序,对吧?跟左右啊,跟呢要打印在前面,左指数了,打印在后面,最后呢打印右指数,那么只是我们拿到了这个入,他要不要打印呢?这个入他肯定是要打印,因为他本身就是一个根结点,对不对?那么这个入他我们怎样? 哎,打你打,打印完了这个入他啊,那么接下来哎应该干什么呢?就这个入他,我们要判断他呢,有没有左指数,对不对?左边有没有,有没有节点啊?如果说他左边要是有的话,那么接着呢,我们就要打印这个 live, 好,打印完这个内部的了,打印完内部的之后,我们接着要打印右边,对不对?那么这个内部的呢,由于他不能够直接找到这个右边,他要通过回速,对不对?要回速找到这个入他啊,找到这个入他之后,再呢来打印这个啊,打印这个 ride, 那么这个是前 连续便利他这个顺序啊,以及他这个在在这个阿扎树这个图里面,他的一个搜索的一个顺序,对不对?首先呢通过根结点找到左指结点,左指结点呢回竖到根结点,然后再找到右指结点,完成呢这一棵树的一个便利。那么这个跟地规又有什么关系呢? 其实实际上啊,我们来看一下啊,那么地规的话,实际上它是有存在一个吊用站,对不对?存在一个吊用站啊,那么首先呢我们会把这个入特,把这个入特节点呢进行入赞, 对吧?我们首先呢拿到这个入腿接点,那么这个入腿接点入赞,此时这个入腿呢,实际上是作为这个赞顶元素,对不对?赞里面呢只有一个元素, 他既是占顶呢,也是占底啊,那么就这个入他就是这个占里面的元素,那么此时这个入他要不要打印呢?他要打印,对不对?那么这个入他他应该要打印出来,打印出来之后这个入他能出战吗?他此时不能出战,为什么呢?因为如果把 这个入口出站了的话,那么我们哎,等会我们找到了这个入口的下一个节点,找到了这个内部的,对不对?那么这个内部的我们要找右节点的时候,我们还要回数了,如果你把这个入口要是出站了,那么这个入口你就找 到了,对不对?你在,你在你这个吊用站里面,这个入他就没有了,所以此时这个入他,他是不可以出战的,不可以出战啊,那么此时呢?如果,哎,这个入他读到了这个内福特了,我们应该把这个内福特压到这个站里面来啊, 把内部的压到这里面来,只是站底是入的,站顶呢,是内部的好,这个内部的入战的,那么这个内部的要不要打印呢?要打印啊,此时内部的是作为一个站顶元素,对不对?那么此时应该打印这个内部的 好,打印完这个内部的之后,那么这个内部的呢?哎,我们还要判断这个内部的到底还有没有左指数,对不对?这个内部的如果有左有左指节点的话,那么还得接着打印,但是只是我们会判断了判, 按照这个内服的他这个桌子结点呢,是一个闹,是一个闹啊,那么这个闹,哎,把它也是哎,同样的把它录到这个站里面来, 这个闹入战的话,那么这个闹嘞,他就不能继续往下,对不对?因为这个闹你再掉他的内服的就要抛空子针了。所以此时我们遇到一个闹接点,这个闹呢,就要要弹出去,对不对?要出战啊,不能让他待到这个战里面啊,那么这个闹弹出去之后,那么就接着呢,这个内服的 重新成为暂停,对不对? leve 的重新成为暂停啊,那么接下来呢,也就意味着了,哎,这个 leve 他发现他的左指数已经弹出去了,那么只是我们就要判断他的柚子数了,对不对?那么这个 leve 的柚子树是什么呢?柚子树同样是闹, 同样是闹,那么这个闹闹了,同样弹出去,那么最后嘞到了这个内服的好,当这个内服的再一次成为占顶元素的时候,这个内服的哎,他发现他的左左指数跟右指数呢,都入过战了,而且呢,已经出战了, 对不对?他也没有必要再往左转往右了啊,左右都已经走过了,那么此时内服的已经没用了,那么这个内服的他就该出战了,对不对?这个内服的他就得出战好, 那么把内部的弹出去之后,那么此时呢,哎,这个暂停元素呢,就变成了什么?变成了 rut, 那么此时这个 rut 呢,他会发现他的左边呢已经便利完了,那么此时就该得去便利他的右边了啊,就是便利他的柚子数,那么此时呢就掉这个 rat 点,哎,这个 rut 点 rat 就到了这个到了这个结, 因此我们会发现,实际上这个情绪便利其实就是一个压站,然后呢一个弹出站的一个过程,对不对?所以说呢,哎,如果明白了这么一个过程的话,那么来看代码了,哎,写起来是比较简单的, 这里呢,韩文老师已经提前的把这个哎代码了,已经写在这里了,就是,呃,先呢把这个塑形结构了,把它构造出来了,这里呢构造了一个简单的竖啊, 呃,这里呢有七个结点,那么这个数的一个结构呢,实际上是这样的啊,首先是一是根结点,一呢指向二三,二呢指向四根五,五呢指向六根七啊,那么,呃,我们来看一下这个代码, 这边这个缺肉的呢,是一个公共类啊,就是里边呢有一个啊,就是节点的直,然后呢节点的左指节点啊,以及他的右指节点,以及这个节点所处的一个深度啊,就是处于第几层啊? 我们的阿扎数呢,他是有一个层级关系的,比如说这种根结点肯定是第一级,对不对?那么往后呢,就是这个是,这是第一层,这是第二层,对吧?然后再往后呢就是第三层啊,再往下呢就是第四层的,那么这个是他的一个深度啊,就是当前这个节点所处的这个层级是几啊? 那么这个是深度,那么再往后呢这三个呢?就是,呃,三个,嗯,构造函数啊,好,那么接着我们看,一呢指向二三对吧?二呢 指向四五啊三,四呢?他是空的啊,我们来看啊,这个三对吧?三跟四,那么都是属于叶子节点啊,然后呢五呢指向六七,好,那么这个是这个二大树的这个结构,那么接下来呢,我们就来使用这个地位啊,按按照我们刚刚画的这个简图啊,来完成这个地位,那我们刚刚讲了这个地位了, 实际上呢就是要进行一个压站,对不对?压站然后出站的一个过程。那么我们首先第一个,我们掉这个方法的时候,掉这个方法,我们把这个漏的一了,把它压到这个站里面去了啊, 很简单例子,我们来看一下这个,那么首先呢,我们哎拿到这个根结点,相当于呢把这个一对吧压到这个站里面来了,好, 一入战了,入战了之后呢,那么这个一要不要打印呢?一要打印对不对?因为我们说了一就是这个一啊,拿到这个一马上就要打印,因为这个一呢,他是最根的这个节点,对不对? 然后呢再往下对不对?然后就根据这个一啊,他去找找他的桌子节点,找到这个二,那么二要不要打印呢?此时啊,这个二我们就要判断一下了, 这个二呢,他只是一个左指节点,那么呢肯定是要打印的,那么我们哎,讲了这个跟左右,我们这个前序便利,对吧? 这个前序便利啊,他是根,然后呢左指节点,然后呢右指节点,那么如果说我读到这个一,一是个根节点是没有问题的,那么 此时读到二,二呢,作为他的左指节点,那么呢,此时答应一,答应二,这个二呢,到底有没有问题呢?这个二该不该答应呢?我们要看一下其他的指数,他是不是也符合这个规则啊? 这个二他是不是一个根结点呢?在这个指数里面,在这个指数里面,实际上他也是一个根结点,如果啊只看这一个指数的话,这个二呢,他也是个根结点,所以说呢,这个二呢,也应该打印,对不对?应该打印这个二, 二前边呢,不应该再有值了啊?因为我们如果只看这个指数的话,那么这个一呢,就没在这个指数里面吧,所以二呢,前边不能够再有值,所以说此时必须打印这个二啊。 好,然后呢再往下,对不对?再往左边啊,再往左边,找到这个四四应该应不应该打印呢?也应该打印,因为这个四,他的这两个,呃,左右指节点呢?同样的在这个指数里边,他呢也是作为一个根结点存在的, 他的左右指节点呢,我们可以把它看成是空,对吧?啊?叫做闹节点,闹节点啊,那么这个四呢,也应该打印,只是应该打印这个四,好,那么只是我们看到看,再看一下这个站里边的结构啊,我们读到了一个二,对不对?读到了一个一,读到了一个二,然后呢读到了一个四, 好,那么我们这个打印的顺序呢,就是读到这个元素就打印,读到这个元素打印,读到这个元素打印,实际上是什么? 实际上是一直打印这个暂停元素啊,所以说前续便利时尚就是打印的暂停,因为我们刚把一放进去的时候,这个暂停是什么?暂停就是一 对不对打印暂停,然后把二放进去了,暂停它变成二了,那么呢打印二,接着呢,把四放进去了,四又成为暂停了,那么打印四,所以说这个就是前序便利,前序便利的话,你拿到一个节点就打印,拿到一个节点就打印啊,从根结点开始,然后呢从左往右啊,所以说这个代码呢,写起来也比较简单的,首先呢,我们就直接呢来一个打印就可以了啊, 先拿一个打印就是我们啊, sout。 然后呢打印这个什么?打印这个 rut 的一个歪柳,打印他的这个歪柳, 他们也就说拿到一个节点就打印嘛,打印完了之后呢,打印完了之后,我们就要从左往右了进行压站,对不对?那么一呢,把他的左节点左指节点压站,把二压进去,二呢?哎,还得把 把他的这个桌子节点把四压进去,那么四呢?四往再再往下呢,实际上他也是有子节点的,只不过呢,他的这个左右子节点呢,都是呢指向了这个闹啊,这个四实际上是有左有有这个子节点的啊, 不要认为那是没有,只不过是说他的左右指针都是指向了一个闹,那么此时这个闹呢,也要进行入账, 那我把这个,把这个闹用到这个站里面来的话啊,这个闹了,就变成这个占顶元素了,对不对?变成占顶元素了,那么变成占顶元素的话,对于这个闹我们没有办法操作,因为它是一个空的,对不对?空的啊,那么此时怎么办呢?这个闹呢,只能出站,必须 出站啊,因为如果不出站的话,我们按照去找左右指节点,他都找不到,对不对?找不到,那么这个闹必须要出站,那么出去之后,那么这个试了,又重新成为了这个,哎,这个占顶元素,占顶元素之后呢?那么呢?哎,又该找他的右右指, 因为左指数已经找完了吗?都出站了,对不对?出站了也意味着他的左边已经找完了,找完了,接着呢就要找他的右边了,对不对?找这个四的右边,那么右边呢?还是一个闹,那么这个闹进来之后跟左叠点是一样的啊,那么进来之后是个闹吗?对不对?没办法,走了就只能够,哎,出站。 出战之后呢,那么接着呢,这个四呢?就变成,哎,又变成暂停元素了,那么变成暂停元素之后,这个四此时呢也得出战, 那么这个四他为什么此时要出站呢?因为他左边跟右边都已经便利完了,对不对?都已经便利完了,所以说了这个四必须要出站,他已经没用了,对不对?没用了,已经便利完了啊, 四了,要出站,那么四出完之后呢,那么这个二就变成占领元素了,那么这个二呢,他会发现他的左边呢已经打印完了,对不对?但是右边还没有打印完,那么此时我们就应该呢把这个五呢,把它入到这个站里面去啊,那么此时这个二能不能出战呢? 不能出站啊,因为他右边的直接点还没有出站的,对不对?刚入站啊,只能往上压,那么我们先呢来完成这一步啊,所以呢,我们在这里我们会发现,如果当一个元素他要是围闹的话,就必须了马上出站,那么作为我们这个地位调用的话啊,作为我们这个地位调用,那么所以呢,我们应该在这里呢加上银行代码, 这样代码是什么呢?如果说这个元素啊本身要是 no 的话,那么马上就要出站,出站呢,直接就是微特 直接返回,对吧?那我们马上就要进行这个地规调用嘛,地规调用啊,就瑞特就意味着了就出战,就这个元素本身啊,他是一个空的,是一个空的,你就没办法去调他的这个, well, 对吧?没办法去调他这个, well, 直接的只能够出战,好,那么出完之后呢? 是不是我们马上呢就要继续调他的桌子节点,对不对?桌子节点怎么怎么找?直接接到地规啊,直接地规 掉这个入他的一个 let, 掉他的 let, 那么通过这么一行代码,我们其实呢直接呢,哎,就把这个一二四啊,这个五了,我们先去掉, 就来到了,来到了这么一个步骤,对不对?那么把一入进去,一的左边的是二,二的左边是四,四的左边呢是闹,那么直到呢,把这个闹入进来,对不对?好, 把这个 no 入进来,我们来看这个代码啊,那么当这一行代码,当这一行代码递归到这个 no 的时候,那么这个 root 啊,这个递归到四的时候啊,四的这个 neff 是 no, 对不对?那么这个 no 呢?哎,他继续递规,这个 no, 递规啊,判断到这里,那么此时这个 root 就等于什么?因为这个四点, let 四点内服的是空,对不对?我们来看上面这个节点啊,四,四这个节点他能,他的 nife 的是闹,所以呢,哎,出战,对不对?哎,对应 我们刚刚这个图里面这一步,这个闹结点出站,好,那么出站之后,我们就要,哎,接着要来编辑他的柚子树,对不对?柚子树,那么接着呢,我们这里呢?哎,又得来一行代码, 柚子树啊,柚子树,也就是这个入他的点呢? rat, 好,这,这个 rat 这一行代码呢,就意味着这一个闹元素进行入账啊,这个柚子数右边的这个指节点进行入账啊,这个呢?是啊呢啊, no, 就是右边的啊, rat 这边呢是 let 好,那么这个节点呢?一样的,进来之后呢,他也是空的,那么他呢?也得出站,也得出站啊,那么也就是对应着我们这里吗?就是这个右边的这个节点呢,同样的调到这里来,那么呢,哎,出站,出站意味着什么?那么此时的这个四呢? 这个我们四这个节点是执行到了这一步,对不对?四,这个节点已经执行到这一步了,那么他的内服的呢?已经作为 空返回了,那么再往下了,四的这个 read 了,他也作为空了,也返回了,那么四本身呢?相当于这两项代码了,已经执行完了,对不对?那么四本身也要出站啊,就对应着我们这一这一步操作,那么四 啊,四就出战,四出完战之后,那么我们这个二还在哪啊?二还在这里,对不对?二还在这里啊, 好,二的这个左边呢,就是四,对不对?四已经出去了,那么接着呢?二就往下直行吧,直行到哪里啊?直行到这个地方,那么就接着要把二的这个右指节点,也就是我们这个五这个节点啊,就是五这个节点,那么要把五这个节点呢?哎,入战, 那么五这个节点,他一入战之后啊,一入战,那么呢五这个节点呢?他接着呢?就会,哎,过来,过来,五的,五的这个 read 了,这个五本身呢?就,当然这个是二,等于 这个入的现在是二,但点 red 呢?是等于五,对不对?那么五进来了,他肯定是不是空,对吧?不是空啊,那么接着呢,就把这个五了打印出来,五打印出来,然后再往下呢,就是五的内服的跟五的 ret, 那么接着就是我们的后面两步压站,就是把这个六了把它压进来。 好,这个六进来之后呢,其实这个六跟四的情况是一样的,对不对?左指接点,右指接点,都是空,那么接着这个六了也要出站,也要出站,那么接着就是七,对不对?接着就是七,七再进来了,出去,再进来,出去啊,那么五了也跟五,这个五了,就跟上面这个二的情况是一样的,那么 五了到了这个他的左右节点出站之后,这个五呢也要出站啊,好,这个五出完之后呢,那么接着到了这个二了,二的话呢,因为这个四跟五都出了,对不对?左右节点都出了,那么二呢也要出站,二出完站之后,一呢成为这个站点元素,那么一的左指节点已经出站了, 接着呢,就这个一呢,他会来到这里,对吧?这个一他就执行到这个地方了,左边的已经执行完了,那么接着来执行这个右一的,这个右边一的右边是多少呢?是三,那么呢把这个三呢再压进来 啊,只是一了不能出站啊,只是一不能出站,那么把三呢压进来好,然后呢三呢?左右直接点为空,那么三弹出去,三弹出去弹出去,最后呢就上顶了,就变成一了一了,再弹出去,那么整个算法呢就结束了,那么这个就是前序便利,所以说呢,前序便利了,还比较简单,对不对?直接呢就把元素一个 一个往里面压,然后一个一个的往里往外面弹,当这个元素他是占顶元素的时候,那么呢就打印这个元素啊,我们来看,其实呢, 其实就是每一个元素当然是暂停元素的时候,其实就答应,比如说我们这个一啊,这个根结点把它放进来的时候,发现呢?哎,这个赞里面 没元素,那么他就是暂停,对不对?把暂停答应,答应啊,好,接着呢压这个二,把二压进来,二呢压进来之后呢,发现呢,他就是占顶元素,那么答应啊,然后接着压这个四,四是占顶元素。答应啊,那么再接着呢来一个 left now, 当然这个 left now 呢是一个空啊,没什么打印的,那么答应不了,那么呢,弹出去 啊,来一个,来一个, rat 也打赢不了,也弹出去。好,接着呢,把这个四弹出去,弹出去。好,这个接着呢,就把这个五压进来,对不对?好,这个五压进来了,他变成占顶元素了,当然这里有一步有一个步骤要注意啊,就是我们这个四弹出去之后,那么这个二呢?他会重新成为占顶元素,对不对?那这是你第二次成为占顶元素,但是 你已经打印过了,我们前序便利的话,实际上是第一次成为占顶的时候进行打印啊,那我们来看这个五了,当你第一次压进来的时候就要打印,对不对?第一次压进来的时候打印,当你,哎,你 第二次这个六出来进来,再出去之后,这个五呢,再一次成为暂停元素,也就是第二次成为暂停,那么这时候应不应该答应呢?不应该答应,对不对?因为你已经打印过了啊,所以说 我们这个前序偏离啊,这个前序偏离。这里写一下啊,前序实际上就是什么第一次成为暂停啊,第一次成为暂停元素, 那即打印,那么这个其实就是前序便利,那么来看这个结果,对不对啊?我们呢?哎,直接运行一下这个面方法, 看一下这个打印的是不是按照了这个前序便利的这个结果。我们呢,先来先呢来估一下这个结果啊,就这个结果很好估,对吧?那么肯定是了,一对不对?一,最先打印,然后呢是二,接着是二,对吧?然后接着呢是三,哎,接着是四啊,接着是四,一二四一二四 四,打印完之后呢,那么接着就要打印这个什么打印这个五啊?打印五这个元素。五打印完了呢,那么就是六 六,打印完的呢就是七,那么最后呢就是三了,七啊,那么最后就是打印这个三,那么我们来看这个结果是不是幺二四五六七三啊? 好,幺二四五六七三,所以呢这个是没有问题的,那么这个呢是呃,使用地规的方法实现这个,呃前序便利。