mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-06 01:15:57 +08:00
44 lines
1.1 KiB
Markdown
Executable File
44 lines
1.1 KiB
Markdown
Executable File
# [230. Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/)
|
||
|
||
|
||
## 题目
|
||
|
||
Given a binary search tree, write a function `kthSmallest` to find the **k**th smallest element in it.
|
||
|
||
**Note:** You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
|
||
|
||
**Example 1:**
|
||
|
||
Input: root = [3,1,4,null,2], k = 1
|
||
3
|
||
/ \
|
||
1 4
|
||
\
|
||
2
|
||
Output: 1
|
||
|
||
**Example 2:**
|
||
|
||
Input: root = [5,3,6,2,4,null,null,1], k = 3
|
||
5
|
||
/ \
|
||
3 6
|
||
/ \
|
||
2 4
|
||
/
|
||
1
|
||
Output: 3
|
||
|
||
**Follow up:**What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
|
||
|
||
|
||
## 题目大意
|
||
|
||
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
|
||
|
||
|
||
## 解题思路
|
||
|
||
- 由于二叉搜索树有序的特性，所以中根遍历它，遍历到第 K 个数的时候就是结果
|
||
|