一【题目类别】

• 二叉树

二【题目难度】

• 中等

三【题目编号】

• 230.二叉搜索树中第K小的元素

四【题目描述】

• 给定一个二叉搜索树的根节点 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 小的值，你将如何优化算法？

八【解题思路】

• 要利用二叉搜索树的特点，对二叉搜索树进行中序遍历就是从小到大的有序序列
• 所以对二叉搜索树进行中序遍历，然后存储在数组中，最后返回第k小的值就很简单了，数组是随机存取结构，可以直接返回
• 如果用C语言写的话需要注意，数组的索引不要使用index作为关键字名称，因为index是C语言的一个函数名，所以会报错重定义，使用其他关键字名称就行

九【时间频度】

• 时间复杂度：$O(n)$，其中$n$为树的结点个数
• 空间复杂度：$O(n)$，其中$n$为树的结点个数

十【代码实现】

1. Java语言版

package Tree;

public class p230_TheKthSmallestElementInABinarySearchTree {

    int val;
    p230_TheKthSmallestElementInABinarySearchTree left;
    p230_TheKthSmallestElementInABinarySearchTree right;

    public p230_TheKthSmallestElementInABinarySearchTree() {
    }

    public p230_TheKthSmallestElementInABinarySearchTree(int val) {
        this.val = val;
    }

    public p230_TheKthSmallestElementInABinarySearchTree(int val, p230_TheKthSmallestElementInABinarySearchTree left, p230_TheKthSmallestElementInABinarySearchTree right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public static void main(String[] args) {
        p230_TheKthSmallestElementInABinarySearchTree root = new p230_TheKthSmallestElementInABinarySearchTree(3);
        p230_TheKthSmallestElementInABinarySearchTree left = new p230_TheKthSmallestElementInABinarySearchTree(1);
        p230_TheKthSmallestElementInABinarySearchTree left1 = new p230_TheKthSmallestElementInABinarySearchTree(2);
        p230_TheKthSmallestElementInABinarySearchTree right = new p230_TheKthSmallestElementInABinarySearchTree(4);
        root.left = left;
        left.right = left1;
        root.right = right;
        int res = kthSmallest(root, 1);
        System.out.println("res = " + res);
    }

    private static int size;

    public static int kthSmallest(p230_TheKthSmallestElementInABinarySearchTree root, int k) {
        size = 0;
        int[] nums = new int[10001];
        inOrder(root, nums);
        return nums[k - 1];
    }

    public static void inOrder(p230_TheKthSmallestElementInABinarySearchTree root, int[] nums) {
        if (root != null) {
            inOrder(root.left, nums);
            nums[size++] = root.val;
            inOrder(root.right, nums);
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

2. C语言版

#include

struct TreeNode
{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
};

int size;

void inOrder(struct TreeNode* root, int *nums)
{
	if (root != NULL)
	{
		inOrder(root->left, nums);
		nums[size++] = root->val;
		inOrder(root->right, nums);
	}
}

int kthSmallest(struct TreeNode* root, int k)
{
	size = 0;
	int nums[10001] = { 0 };
	inOrder(root, nums);
	return nums[k - 1];
}

/*主函数省略*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

十一【提交结果】

1. Java语言版
   

2. C语言版