题目描述（中等难度）

给一个二叉搜索树，找到树中第 小的树。二叉搜索树的定义如下：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 任意节点的左、右子树也分别为二叉查找树；
3. 没有键值相等的节点。

思路分析

通过前边 98 题 、 以及 108 题 的洗礼，看到二叉搜索树，应该会立刻想到它的一个性质，它的中序遍历输出的是一个升序数组。知道了这个，这道题就很简单了，只需要把中序遍历的第 k 个元素返回即可。

解法一 中序遍历

说到中序遍历， 已经讨论过了，总共介绍了三种解法，大家可以过去看一下，这里的话，直接在之前的基础上做修改了。

总体上，我们只需要增加两个变量 num 和 res。num 记录中序遍历已经输出的元素个数，当 num == k 的时候，我们只需要将当前元素保存到 res 中，然后返回即可。

下边分享下三种遍历方式的解法，供参考。

递归改写，压栈法。

常数空间复杂度的 Morris 遍历，94 题 对 Morris 遍历有详细的解释。

可以看到，三种解法都是一样的，我们只是在中序遍历输出的时候，记录了已经输出的个数而已。

解法二 分治法

如果不知道解法一中二叉搜索树的性质，用分治法也可以做，分享 的解法。

我们只需要先计算左子树的节点个数，记为 ，然后有三种情况。

n加 1 小于 k，那就说明第 小的数一定在右子树中，我们只需要递归的在右子树中寻找第 k - n - 1 小的数即可。

n 加 1 大于 k，那就说明第 k 小个数一定在左子树中，我们只需要递归的在左子树中寻找第 k 小的数即可。

总

解法一的前提就是需要知道二分查找树的中序遍历是升序数组，问题就转换成中序遍历求解了。解法二的话，属于通用的解法，分治法，思路很棒。

添加好友一起进步~

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情