如何根据root表画最优二叉搜索树

让我们看一下这题，就是给定一颗二叉数，先找出 dk 格大的节点， dk 大的节点的时候就是这是一个二叉搜索数 dk 大的节点，你像这个 k 等于一的话，他输出的是四。就这个就是完差错数 k 等于三的话，他输出的是四。有这题啊，我感觉这个最近写的比较好。就说嗯， 他二叉数数低， k 大的节点可以转换为此数中序变，因为二叉数数他中序 便利，他为递减的序列。就此处的中序边离道序的 dk 的接点。就说二叉数的时候， dk 大的接点，客串号也此处中序边离道序的第 k 个接点。因为他是递减的吗？ 有倒雪的第 k 个系列就是四。就。我们知道中学面临就是特别简单，一个是地规的中字条件，就是嗯，在中间打印这个外六字就拍成的话，嗯。最后就是地规的话，就是要有中字条件，地规，嗯， 低规的这个。呃，逻辑就一个是作用条件。还有就是这个低规之后就是嗯。看一下他写的这个。就是 这题的接法。就是首先是先进行先写这个 dips， 就是先进行这个地规的这个优字数，之后如果就是地规的终极条件，就是到头了就直接返回。之后就 是柚子树说就是就是他的这个嗯，相当于打印这个中间地点。实际上就找到几 k， 怎么找呢？就说如果 k 等于零之间返回，否则的话就可以不断的减一，一直找到这个可以等于等于零的时候，把这个为六直复制一下，之后返回。 就这题啊。实际上这这种写不是很写的，不是很直观，比较直观的写法就是说我就是 地规，就是地规之后你可以用这个站去写，之后就是把它不断的然后送入到这个站里面，之后就是嗯，找到这个 dk 了。就也是这种中序的想思路就是 啊，找到 dk 了之后减去这个之后谢谢大家。

白话数据结构的第九集我们来讲一下什么是白内心 tree 二叉搜索数。首先，在工作中，当我们提到这个数据结构的时候，我们一般会用 b s， t 来把它的简称。 b s t 需要满足两个属性。第一， b s t 是一个二叉数。第二，如果 n 代表 b s、 t 中的任意一个节点， l 代表 n 的左边 such 中的任意节点，而代表 n 的右边 sub tree 中的任意节点。那么我们有 l 小于等于 n， 小于等于 r。 这如果用人话解释，这是左边的，小于等于右边的。 我们以这个数作为一个例子。现在我们让 n 等于六，那么 n 左边的 surpree， 这个 surpree 中的任意一个节点都比六小，右边这个 surpree 中的任意节点都比六大。但是我们这里不仅要观察顶端的这个点，还要观察每 一个节点。比如这里三，他左边的三不是一是一。右边包含了四和五，一小于等于三，三小于等于四，并且小于等于五。 当一个二岔数中的所有节点都符合这个特性的时候，我们就可以说这个二岔数是一个 bst。 那么二叉搜索数对比普通的线性数据结构有什么优势呢？ 假设我们会一个一个得到右边的这些数据，接下来我们尝试将这些数据放进一个二叉搜索数的同时，放进 r 里面，插入新元素。这个行为在二叉搜索数中有 o log n 的时间复杂度，但是在下面这个 r 中只有 o 一的时间复杂度。我们首先插入九， 然后六，六需要和九对比，他去了左边，七需要和九对比，反显其比九小，但是比六大，所以他到了这。我们还是哦。一插入下一个四对比九比九小， 比六小，随四到了这。欧一进入了二位，十二比九大，随他到了右边。欧一进入了这个二位，十五到了这里，十五到了这 十四比十二大，比十五小，所以到了这十四到了这。这样我们就将所有元素放入了这两个数据结构中。我们可以观察到，构建上面这个数的时间复杂度是长于下面这个时间复杂度的， 因为每一次插入我们需要 olog， 而下面这个插入只需要 o 一。下面让我们来查找十五是否存在于这个数据结构中。我们先从二位开始，十五需要先和九对比，再和六、七四、十二、十五。在这里我们已经经过了六次对比。那么如果在二查搜索书中呢？ 我们十五比九大，所以去到了右边，比十二大去到了右边。我们发现十五存在于这个数据结果中，只用了三步。所以 我们搜索的时间复杂度在这是 log n， 而在下面是 n。 我们可以把 bst 的优势理解为它是一个天然的排序数据结构。 bst 可以处理简单数据结构，也可以处理复杂数据结构。我们以 ologon 的写入时间复杂度 保证了这个数据结构在任何时候都是排序的。 dfs 的 in order traversal 就是排序。使用这种数据结构的方法，数字的排序时间复杂度是 on。 复杂数据结构的排序时间复杂度是 o n 辣根。所以我们牺牲了写入的时间复杂度，得到了排序的数据结构，并且将查找的时间复杂度从 n 降低到了辣根。

二叉数的三种病例方法，先序、中序和后序。如果你去做 c 元的笔试题，这个代码务必牢记老规矩，先搞清楚原理再去写代码。所以先序病例就是按照根左右的顺序来访我们一个节点。 比如有这样一棵阿沙树，先访问根结点一，然后是左边的结点二，但是二又可以作为这棵子树的根结点，所以下面还不能去访问三。 如果二作为根节点，那他的左孩子就是四，同理四也是这棵子树的根，所以再去访问八八的下面没有孩子节点，这才轮到四的右孩子，就是九 四八九都已经访完了，相当于二的左边便利结束，按照跟左右的顺序继续访问二的右边，于是得到了五和十一的左边便利完了，轮到一的右边就是三六七，这个结果就是使用先序便利得到的结果。 对于人来说，看起来可能没有一二三四五六七八九十来的直观，但是代码写起来却非常的方便，写先去便利之前，起码先得有一棵二叉树才行。创建二叉树的方法有很多，不同的应用场景，使用的方法也不一样。 这里给大家介绍一种比较简单的，先是一个数组，数组有十个元素，然后来十个节点，记录下每个节点地址数据，填上对应的数值，最后只要操作 left 和 right 指针，让他们形成数的关系，就成了一棵完全二叉树。 那他说的特点是一层一层向下延伸，所以用地规非常合适。地规的结入条件就是他不存在含字节点。先访问根节点，然后对左子数和右子数做同样的操作，调相同的函数参数，一个是左子数的根，一个是右子数的根，代码非常的简单，结果跟我们刚才 分析的也一样，知道了先序便利，那中序便利和后序便利也就非常简单了。中序便利的顺序是左跟右，代码中只要调整一下访问语句的位置就行。后序便利，顺序是左右跟，先访问左子数，再访问右子数，然后打印跟结点。 最后，关于阿叉叔的便利，给大家留一个非常经典的笔试题，已知阿叉叔的先续便利和中序便利，求后续便利。如果你知道答案或者解题思路，欢迎在评论区交流。

大家好，我们来认识一下二叉数的便利，正常来说，二叉数一般分为前序便利、中序便利和后续便利。前序便利就是说我们先便利根结点，然后再便利他的左指数，最后再便利他的右指数， 然后中序便利。到一个节点的时候，我们先便利该几点的左子数，然后再便利该几点，最后再便利该几点的右子数， 然后后续便利。就是说当我们到某一个节点的时候，我们先便利该节点的左指数，然后便利该节点的右指数，最后才便利当前节点。以上就是二叉数常见的三种便利方法，大家好，今天我们认识一下面试今天一百五十题，你可自私二叉数的前序便利，给你一个二叉数的跟节点 retur 返回他节点值的前序便利 五下。有一个二叉数，我们用它来模拟一下该算法的实现，该算法最简单的方法，我们可以用地规实现，我们指向一个节点的时候，我们先便利当前节点，然后在地规便利它的左节 点和它的右结点。低规算法很容易理解， 因为在地规的过程中使用了系统站。第二种，我们就用站来模拟一下这个过程，最开始我们拿到入团是五，然后当前节点我们入站， 当前站点是五，我们出站。出站过后，我们需要便利当前助站的节点五，然后勿站前去便利。由于我们需要先便利他的左子数，再便利他的右子数，所以我们先要右子数助站，然后再左子数助站，所以这个时候就是 右指数先入站。七入站，然后是他的左指数。三，几点入站，然后就是入站过后，然后就轮到下一次，下一次循环就出站，然后就三出站，三出站的时候便利当前几点， 三，然后判断是否需要入站。三有左右子节点，然后是三的右节点，四节点入站，然后三的左节点。二入站，入站过后，然后下一次循环，这个时候就是二 二出站，出站过后要便利当前节点，当前节点为二，然后判断是否需要入站，由于二没有左右子节点，所以不用入站，然后当前循环结束，然后再出站， 出站过后便利当前节点，然后再判断节点四是否有左右子节点需要入站。四没有左右子节点，所以不用入站，然后下一次，然后七出站，便利当前节点，然后再入站。七有左右子节点，所有七的右子节点。八先入站，然后是七的左子节点，六入站，然后下一次循环，然后是六出站，出站过后便利， 然后再判断六节点是否有左右子节点，他没有，所以不用入站，然后是下一次八出站，八出站过后便利，然后再判断八节点是否有子节点，八也没有子节点，所以不用入站，然后下一次循环，然后我们的 占为空，便利结束，所以前续便利的一个结果就是五三二四七六八，该算法的时间复杂度为 o n， 空间复杂度也为 o n， 大家理解了吗？

哈喽，大家好，欢迎来到大厂高频面试算法题分享，每日一题，快 at 你的冤种朋友来学习吧！二叉数的最大深度 广度优先搜索从根节点开始，将节点加入到队列中，此时队列里存放的是当前层的所有节点。 每次从队列里拿出所有节点，将节点的下一层节点加入到队列中。保证每次添加完的时候，队列里存放的是当前层的所有节点。 用 result 来记录往队列里添加节点的次数，就是二叉数的最大深度。看完啦，点个赞再走吧！

大家好，这里是代码所养路，我是程轩卡尔，这期视频呢，来给大家讲解代码所养路中二叉数章节的翻转二叉数啊，那这道题目呢，其实是面试中呢，也比较常见的啊，比较简单的题目啊， 但即使这么简单的题目呢，经常有很多同学呢写不出来啊，那我们先来看一下这道题的提议啊， 那就是给一个这个二叉数啊，然后我们如何翻转呢啊，其实就是以这个为中轴线啊，给他这么，给他这么翻转过来啊， 翻转过来啊，那大家可以发现，其实呢，就是两两去交换啊，这个节点的左右孩子啊，注意啊，这里边交换左右孩子呢，交换的是指针啊，不是交换数值啊。例如说，这里二和七 七做交换之后，二这个节点下面的左右孩子也是跟着交换过来的啊，也是跟着交换过来的，然后这个一和三再做交换啊，变成三和一啊。很多同学可能感觉，哎，我这交换两个节点，我这个数值交换一下不就得了吗？啊， 其实这里边是啊，指针做交换啊，也就是说你二如果交换到右面来的话，你下面的左右孩子也是跟着交换。那么这道题目呢，应该不少同学呢，都已经做过了，但是大家发现，哎，做过之后，过一段时间，哎，这道题目好像又写不出来了啊。 因为大家在写这道题目的时候呢，其实有很多点是没有想清楚的啊，例如说，这道题目应该用哪种便利方式啊？那两大类便利方式啊，一个是地规，还有一个是非地规，是吧？那 地规里边还有前中后续啊，你是哪种顺序来便利呢啊？很多同学呢，可能哎，我用地规的方式写出来了，我也不知道我是前中后续，反正一提交通过了，哎，完事下一道题目啊， 其实呢，你要把这些想清楚之后，这道题目基本上就是送分题啊，如果大家呢对便利顺序都没有想清楚，就把这道题给 a 过了啊，那下次你再做这道题目的时候啊，大概率可能还是不会啊。 那接下来呢，我们来看应该用哪种便利顺序呢啊，那其实这道题目啊，用前序 和后续啊是最合适的啊，用中续便利啊，比较不方便，也不能说是不方便吧，就代码写的比较绕啊，用前续和后续是最直。 那么接下来我们来写一下代码，来看一下前序和后续来怎么写。然后呢，我们再介绍一下，为什么用中序便利来写这么绕，那这里呢，我写的呢，是类似于 c 加的尾代码其他语言的版本呢，大家可以去代码所有网站上去看本期视频的文字讲解版。 那本期视频呢，我给大家主要就是讲解啊，地规便利中的这个写法啊，至于非地规还有程序便利，依然可以把这道题给通过啊，那具体写法呢，我都写在了啊我的代码所有录网站上啊，大家呢可以去看一看啊。 那首先呢，我们在写代码的时候呢，就要明确啊，既然是写地规吗，我们要想着啊，地规三部曲是吧。啊，那第一步是什么呀？第一步呢，是确定 地规函数的返回值和参数，那这道题目呢，地规函数的返回值，其实这道题目本来就是让我们要求返回这个翻转之后啊，新的二大数的跟结点吗？那所以说我们的这个函数的返回值呢？那就是这个呃 节点的定义啊，然后呢我们是定义这个函数 revert three 参数是什么呢啊？参数其实就是我们传入的分解点嘛，对吧？那这样呢，我们第一步就完成了，然后呢就是第二步， 第二步就是确定中指条件啊，那中指条件我们在便利这个二叉数的时候，什么时候我们应该中指便利呢啊？很明显是碰到空结点的时候我们就中指便利吧啊啊，我代码稍稍往这边 写一写啊，也就是说如果我们的 root 等于等于 no 的话啊，我们就 return 了啊，如果这个根结点呢等于 no 的话呢，我们就啊 return root 啊， 我们就做一个返回的操作啊。当然如果你这个如果你这个二叉数呢，他本来就是一个空的二叉数，那 我传进来的 root 呢？本来就等于闹，那我们我们就把这个 root 呢啊原封的去返回就可以了啊。 那么接下来呢就是这是第二步啊，确定啊这个终止条件，那么第三步呢，就是我们的处理逻辑啊，那处理逻辑呢？我们先写这个前序便利啊，前序便利呢是中左右啊，那中间呢就是我们要 处理的地方啊，我们要处理是什么地方，我们要处理的是什么逻辑？我们要处理的是交换这个节点的两个孩子吧，对吧？交换入他的入他的左孩子和入他的右孩子 两个孩子做一个交换吧。啊这里呢其实这个变量命名为 rot 呢，感觉会对很多同学呢会有一些理解上的一个误差啊，因为粒扣上他给你写好的一个定义，他写就是 rot， 所以说我这里呢就跟着写 rot 了啊，其实你到 rot 下面进行便利的时候入的是指你便利的每一个节点啊，得操作的这个变量啊，他不一不一定真正的是这个二茬树的这个根结点啊，其实这个变量呢，最好不要起入的啊，我只不过是 啊以那个立扣上他的定义这个标准来了啊，那么我们中间的这个顺序就是啊，中间的这个逻辑呢，就是要交换左右孩子啊，交换入他的左右孩子啊， 对吧？啊，然后呢，就是左右左右是什么呀？就是我们的一个啊，便利方向嘛啊， invert invert tray， invert tray 是不是向左去便利啊， 然后呢 invert tray 向右去便利， 哎，那这样呢，其实呢，我们就啊把这个翻转二叉数的代码给写完了啊，那大家可以看，这是中左右啊， 这就是我们啊前序便利的逻辑啊，就是中左右啊，很多同学呢就把这个代码写出来了啊，也不知道自己用的是哪一种的便利顺序啊。那问题来了哎，就是这个 swip 我放在这里，我放在这个中间，可不可以我放在这个下面，可不可以啊？ 一些同学呢，写这道题目或者是看啊，很多题解呢，其实题解上呢，没有跟大家说这个题解采用的是什么便利顺序，有的呢是所以放在这里啊，有的呢是把所以放在这里啊，放在左右的下面啊，往后一提交啊，也通过，对吧？哈， 其实你把所谓放在下面的话，就是左右中啊，那么这个便利顺序呢？就是后续便利，对吧？啊，那也就是我刚才说前续便利和后续便利都是可以的，但是有同 同学呢，哎，想着，哎，既然我放在下面可以，我是不是可以把这个所以吧，也就是交换左右啊，两个节点的这个逻辑呢？我给他放到中间呢，我放在这里可不可以呢？哎，我就来个中序啊，是不是也可以啊？ 其实是不可以的啊，我在这里给大家举个例子啊，例如说我这个中序便利啊，中序便利是左中右吧，对吧？啊，那么我便利这个二叉数的时候，我是先向左便利，向左向左便利，然后在这呢遇到空间我返回啊，到二的这个时候呢， 我这个左中右啊，到二的时候我去交换二这个左右孩子此时变成什么呀？变成四二七三一，对吧？啊，这里是六和九八啊， 这个二招数呢，这个交换了二的左右孩子三合一，对吧，然后呢，我再回退回，退到四这里呢，我继续做这个左右交换的逻辑，那此时变成什么了？变成七六九 二三一，是不是我把这个四个左右孩子给交换了，那是不是变成这个二的数了啊？那因为我中序是左中右，那么我交换完这两个左右孩子之后，我是不是要变利我的右子数了呀？ 那辩解我的右子数的时候发现，哎，这个二三一我是不是之前刚处理过？那我接下来又处理二三一了，左子数相当于是我根本就没有处理它，本来一开始呢，我这个处理的就是左子数，但是我在处理四交换左右节点 之后呢，他俩交换位置，因为我是左中右，我又去便利右了，那此时这里我又去处理原先这个二叉数的左子数了，相当于是原先这个二叉数的右子数，我就一直没有处理啊，所以说这就是啊，使用中序便利化大家会遇到的问题， 那么使用中序便利代码也可以写，那怎么写呢？如果我把这个 three 交换啊两个节点逻辑写在中间的话，那么我这个右呢，其实他就不是严格的右了。我这里呢，继续还处理左子数， 为什么还处理左子数？因为我在这里呢，他交换完之后啊，此时他的右子数是我原先的这个左子数，是吧，那这个的左子数才是我啊真正 想要处理的柚子树。那此时呢，我应该继续再处理左子树，也就是说到这的时候，我继续还处理左子树，才能把这个七六九的这个啊去做对应的处理啊。 那这样呢，其实就是你就可以把这个啊 three 交换两个节点逻辑写在中间了，只不过这里你依然要写成啊这个向左子数的一个边边啊。那这样呢，你就用中序来去写这个代码。当然了，我不建议大家去 绕这个弯子去写中句啊，很容易给自己踩坑啊，如果你理解的呃不够深刻的话，你写的话很容易就给自己绕进去了啊，大家只要记住这个前序和后续写法就可以了啊。就是，所以说要不然就写在这个左 右的上面，要不然就写在左右的下面。这样呢，我就给大家介绍了地规便利中前序、后序和中序便利的这三种写法，那当然了，那个程序便利也可以， 然后非地规便利也可以啊。我在代码算录网站上二叉数章节翻转二叉数本期视频的文字讲解版呢，都给了具体的这些写法的代码，基本上大家想到的写法我都给大家实现了，大家可以去看一看，同时那里呢也有其他语言的版本啊。 那好了，那这期视频呢，我们就讲解到这里了，这里是代码孙杨璐，我是程序员卡尔，感谢大家的三连支持！