561，二叉搜索树中第K小的元素

博哥数据结构和算法 2022-05-10

Instead of holding on to those who have already left, cherish those who stayed behind.

与其执著于谁当初离你而去，不如感谢谁最后留了下来。

问题描述

来源：LeetCode第230题

难度：中等

给定一个二叉搜索树的根节点root，和一个整数k，请你设计一个算法查找其中第k个最小元素（从1开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

提示：

树中的节点数为n。
1<=k<=n<=10^4
0<=Node.val<=10^4

中序遍历解决

这题说的是取二叉搜索树的第k小的元素，做这题之前首先要明白什么是二叉搜索树。wiki百科上对二叉搜索树是这样定义的：

二叉查找树（英语：Binary Search Tree），也称为二叉查找树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
任意节点的左、右子树也分别为二叉查找树；

二叉搜索树有一个非常重要的特性就是：二叉搜索树的中序遍历结果一定是有序的。有了这个特性这题就简单多了，我们只需要按照中序遍历的顺序，取他的第k个元素即可。

二叉树的中序遍历之前讲过，有递归的，非递归的，还有Morris，这里就不在重复介绍，具体可以看下

373，数据结构-6,树

488，二叉树的Morris中序和前序遍历

我们随便挑一个，比如二叉树中序遍历的递归写法如下

1public void inOrderTraversal(TreeNode node) {
2    if (node == null)
3        return;
4    inOrderTraversal(node.left);
5    System.out.println(node.val);
6    inOrderTraversal(node.right);
7}

我们来对他进行修改一下，就是这题的答案了

 1int target = -1;
 2int count;
 3
 4public int kthSmallest(TreeNode root, int k) {
 5    count = k;
 6    inOrderTraversal(root);
 7    return target;
 8}
 9
10public void inOrderTraversal(TreeNode node) {
11    if (node == null)
12        return;
13    //访问左子节点
14    inOrderTraversal(node.left);
15    //访问当前节点，如果访问到第k个就把target赋值
16    if (--count == 0) {
17        target = node.val;
18        return;
19    }
20    //访问右子节点
21    inOrderTraversal(node.right);
22}

统计节点个数

因为是中序遍历，先统计左子节点的个数，

如果左子节点的个数大于等于k，说明要找的元素就在左子节点中
否则如果左子节点的个数加上当前节点个数（1）等于k，说明当前节点就是要找的元素，直接返回即可。
否则我们要找的元素在右子节点中，直接到右子节点中查找。

 1public int kthSmallest(TreeNode root, int k) {
 2    //先统计左子节点的个数
 3    int leftCount = countNodes(root.left);
 4    if (leftCount >= k) {
 5        //如果左子节点的个数大于等于k，说明我们要找的元素就在左子节点中，
 6        //直接在左子节点中查找即可
 7        return kthSmallest(root.left, k);
 8    } else if (leftCount + 1 == k) {
 9        //如果左子节点的个数加当前节点（1）正好等于k，说明根节点
10        //就是要找到元素
11        return root.val;
12    } else {
13        //否则要找的元素在右子节点中，到右子节点中查找
14        return kthSmallest(root.right, k - 1 - leftCount);
15    }
16}
17
18//统计节点个数
19public int countNodes(TreeNode n) {
20    if (n == null)
21        return 0;
22    return 1 + countNodes(n.left) + countNodes(n.right);
23}