中序遍历一棵二叉排序树可以得到

算法：搜索 　　搜索 　　搜索相关的问题，可以有两类任务，查找和遍历。查找 无序查找 顺序查找二叉搜索树有序查找 二分搜索遍历 深度优先遍历（栈的应用）广度优先遍历（队列的应用）

　　查找 　　顺序搜索（Sequential Search） 　　在无序记录集
中搜索关键词为的记录
在记录集中的位置. 它的查找过程是：从第一个开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个记录，其关键字和给定值比较都不等时，则没有所查的记录，查找不成功 　　从前往后找，如果到末尾都没有找到就没有找到。可以看到，这个数从头找到尾都没有找到该数，说明查找不成功；这个数从头找到尾的时候找到了，下标为，返回所查找的记录。 　　顺序搜索也叫暴力搜索，其时间复杂度为, 是列表的长度。可以看到这种时间复杂度是比较高的，那么对于无序数组而言，是否能够通过某种方式使得搜索更快一些呢？答案是可以构造二叉搜索树，然后再进行查找，能够将查找时间复杂度变为 　　二叉搜索树(Binary Search Tree, BST) 　　二叉搜索树又称二叉排序树。它或者是一颗空树，或者是具有以下性质的二叉树：若它的左子树不空，则左子树所有结点的值均小于它的根结构的值若它的右子树不空，则右子树所有结点的值均大于它的根结构的值它的左右子树也分别为二叉搜索树没有键值相等的结点 　　首先通过递归的方式定义二叉搜索树：53，根节点设置为53； 53后面跟的是78，由于78大于根节点53， 78节点设置为根节点53的右子节点； 78后面跟的是65，由于65大于根节点53，则表明65位于53的右子树，又由于65小于78，则65可以设置为78的左子节点； 65后面跟的是17，由于17小于根节点53，则表明17位于53的左子树，17可以设置为53的左子节点； 17后面跟的是87，由于87大于根节点53，则表明87位于53的右子树中，又由于87大于78，则87可以设置为78的右子节点； 87后面跟的是9，由于19小于根节点53，则表明9位于53的左子树中，又由于9小于17，则9可以设置为17的左子节点； 9后面跟的是81，由于81大于根节点53，则表明81位于53的右子树中，又由于81大于78，则81位于78的右子树中，又由于81小于87，则81可以设置为87的左子节点； 81后面跟的是45，由于45小于根节点53，则表明45位于53的左子树中，又由于45大于17，则45可以设置为17的右子节点； 45后面跟的是23，由于23小于根节点53，则表明23位于53的左子树中，又由于23大于17，则23位于17的右子树中，又由于23小于45，则23可以设置为45的左子节点； 23后面跟的是67，由于67大于根节点53，则表明67位于53的右子树中，又由于67小于78，则67位于78的左子树中，又由于67大于65，则67可以设置为65的右子节点； 　　最终构建的二叉搜索树如下图搜索：

　　可以看到：二叉搜索树的中序遍历就是顺序序列: 　　二分搜索(Binary Search) 　　在有序记录集中，每次把待查区间中间位置记录
的关键词与比较，若不等则缩小搜索区间并在新的区间内重复上述过程，直到搜索成功或者搜索区间长度为0 （搜索不成功）为止。 　　可以看到序列是有一个有序的，从小到大排序。 　　查找96：left是12，right是96，mid是54，可以看到mid的值小于96，表明位于右半段，left+=1left是60，right是96，mid是75，可以看到mid的值小于96，表明位于右半段，left+=1left是82，right是96，mid是82，可以看到mid的值小于96，表明位于右半段，left+=1left是96，right是96，mid是96，可以看到mid的值正好等于96，返回该下标； 　　查找24:left是12，right是96，mid是54，可以看到mid的值大于24，表明位于左半段，right-=1left是12，right是37，mid是23，可以看到mid的值小于24，表明位于右半段，left+=1left是23， right是37，mid是26，可以看到mid的值大于24，表明位于左半段，right-=1left是23，right是26，mid是23，可以看到mid的值小于24，表明位于右半段，left+=1left是26，right是26，mid是26，可以看到mid的值大于24，表明位于左半段，right-=1left是26，right是23，由于left>right，这个表明查找完毕，26不在该列表中； 　　遍历 　　深度优先搜索 　　假设
以为起点（源点）进行搜索。 首先标识为已访问结点，接着寻找与相邻的结点,若是未被访问结点，则以为起点进行深度优先搜索，若是已被访问结点，则寻找其它与相邻的结点，直到与有路径相通的所有结点都被访问过. 　　深度优先搜索： 是栈的思想，先入后服务



　　深度遍历： 　　以
为起始，遍历
，再去遍历
连接的边节点
，再去遍历
的边节点
，再去遍历
的边节点
， 再去遍历
的边节点
和
，但是这两个边节点已经遍历过来，所以略过，回到边节点
，继续遍历边节点
， 遍历
的边节点
，遍历
的边节点
，
已经遍历过，继续遍历
，
遍历过，继续遍历
边节点，遍历
的边节点
， 由于
已经遍历过，继续遍历
节点，由于
遍历过，回到
，由于
遍历过，回到
，
遍历过，回到
，由于
遍历过，活到
，由于
遍历过，回到
， 由于
遍历过，回到
， 由于
遍历过，回到
， 由于
遍历过，回到
， 由于
遍历过，返回整个遍历的列表
　　广度优先搜索 　　假设
以为起点（源点）进行搜索。 　　首先标识为已访问结点，然后访问的邻接点
,的未被访问的邻接点，以此类 推，直到与有路径相连的所有结点都被访问到。 　　广度优先搜索：是队列的思想，先来先服务



　　层序遍历： 　　准备一个队列和一个哈希表，队列用来存储遍历的节点，哈希表存储该节点是否被遍历过。首先以
为起始，遍历
，
入队列，发现这一层就这一个节点, [
]；该队列pop出该节点
，再遍历
的子节点，
和
， 如果两个节点都没有被遍历过，这两个节点入队列queue, [
,
]第二层有两个节点，首先队列pop出
， 再遍历
的子节点
，
，
， 由于
已经遍历过，只将
和
入队列 [
,
,
]。队列再pop出
， 再遍历
的子节点
，
，
，由于
已经遍历过，只将
和
入队列queue， [
,
,
,
]第三层有四个节点，首先队列pop出
， 再遍历
的子节点
，
， 由于
已经遍历过，只将
入队列 [
,
,
，
]。队列再pop出
， 再遍历
的子节点
，
，由于
和
已经遍历过，不将
和
入队列queue， [
,
,
] 。队列再pop出
,再遍历
的子节点
，
，由于
和
已经遍历过，不将
和
入队列queue， [
,
] 。队列再pop出
,再遍历
的子节点
，
，由于
和
已经遍历过，不将
和
入队列queue， [
]第四层有一个节点，首先队列pop出
， 再遍历
的子节点
，
，
，
, 由于这些节点已经遍历过，不再入对，最终队列为[]，表明遍历完毕，返回整个遍历的列表
　　学习视频 　　https://tianchi.aliyun.com/course/932/14645 　　排序搜索是非常热门的问题，熟练掌握二分查找法，二叉搜索法，DFS，BFS等算法。 　　例题 　　360 二分查找 　　给定一个 个素有序的（升序）整型数组 和一个目标值 ，写一个函数搜索 中的 ，如果目标值存在返回下标，否则返回 。 　　示例 : 　　解题思路：顺序查找：从头找到尾，如果中间找到则返回结构，如果遍历完毕都没有找到，返回-1，时间复杂度为
二分查找：由于序列是一个有序序列，可以利用该性质，设置左右两个节点，每次取中间值与之进行比较，如果大于中间值，表明是位于右半部分，如果小于中间值，表明位于左半部分，如果相等，则返回下标，时间复杂度为
。 　　python实现 　　C++实现 　　30 搜索旋转排序数组 　　整数数组 按升序排列，数组中的值 互不相同 。 　　在传递给函数之前， 在预先未知的某个下标 （）上进行了 旋转，使数组变为 （下标 从 0 开始 计数）。例如， 在下标 处经旋转后可能变为 。 　　给你 旋转后 的数组 和一个整数 ，如果 中存在这个目标值 ，则返回它的下标，否则返回 。 　　示例 ： 　　解题思路：顺序遍历：从头开始遍历，如果找到该素就返回下标，如果没有找到该素就返回-1，时间复杂度为
二分查找法：由于该列表最开始是有序的，然后经过旋转之后变成不是顺序序列，但观察规律可以看到，序列被分为了两段式有序，还是可以应用二分法来进行查找：

　　python实现 　　c++实现 　　78 二叉树的中序遍历 　　给定一个二叉树的根节点 ，返回它的 中序 遍历。 　　示例 1：

　　示例 2： 　　示例 3： 　　示例 4：

　　示例 5：

　　解题思路：递归方式：树的方法一般是使用递归的方式进行解决，中序遍历，可以先递归遍历左子树，再是根节点，再递归遍历右子树，最终结果就是中序遍历迭代方式：深度优先遍历，先深度优先中序遍历左子节点，然后加入根节点，之后深度优先中序遍历右子节点。一直往左找，往栈中放素，直到找不到下去，栈pop一个素出来，继续找。 　　递归实现python 　　c++实现 　　时间复杂度与空间复杂度最差的情况下都为
　　迭代实现dfspython实现 　　c++实现 　　85 对称二叉树 　　给你一个二叉树的根节点 ， 检查它是否轴对称。 　　示例 1：

　　示例 2：

　　解题思路：递归方式：如果根节点具有左右节点，判断二者素是否相等，如果相等，递归判断左右节点的情况，同步移动两个指针遍历树，p指针左移，q指针右移，每次检测当前p和q节点的值是否相等，如果相等再判断左右子树是否对称迭代方式：层次遍历，bfs，如果是轴对称树，则该层的列表是也是轴对称 　　递归实现python实现 　　c++实现 　　迭代bfs实现 　　首先引入一个队列，初始化时把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。python实现 　　c++实现 　　170 二叉搜索树中第K小的素 　　给定一个二叉搜索树的根节点 ，和一个整数 ，请你设计一个算法查找其中第 个最小素（从 1 开始计数）。 　　示例 1：

　　示例 2：

　　提示：树中的节点数为 。 　　进阶： 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 小的值，你将如何优化算法？ 　　解题思路： 　　基于二叉搜索树的性质，二叉搜索树的中序遍历左根右是一个有序序列。因此先中序遍历，找到第k个小的素即可。中序遍历的方式有递归和迭代，这里使用迭代的方式，就不需要遍历完整个树后，再去遍历序列找第小的素。python实现 　　c++实现 　　进阶 　　如果二叉搜索树经常被修改，这个时候就需要记录子树的结点数。 　　在方法一中，我们之所以需要中序遍历前 个素，是因为我们不知道子树的结点数量，不得不通过遍历子树的方式来获知。因此，可以记录下以每个结点为根结点的子树的结点数，并在查找第 小的值时，使用如下方法搜索：令等于根结点，开始搜索。对当前结点进行如下操作： 如果的左子树的结点数小于 ，则第小的素一定在的右子树中，令等于其的右子结点，等于 ，并继续搜索；如果的左子树的结点数等于 ，则第小的素即为，结束搜索并返回即可；如果的左子树的结点数大于 ，则第 小的素一定在的左子树中，令等于其左子结点，并继续搜索。 　　在实现中，既可以将以每个结点为根结点的子树的结点数存储在结点中，也可以将其记录在哈希表中。python实现 　　c++实现