LeetCode 230. 二叉搜索树中第 K 小的元素
题目描述
思路分析
要在二叉搜索树中找到第 K 小的元素，可以进行中序遍历，因为中序遍历会按升序访问二叉搜索树的节点。
在遍历过程中，记录访问的节点数，当访问到第 K 个节点时，就找到了第 K 小的元素。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func kthSmallest(root *TreeNode, k int) int {
var stack []*TreeNode
node := root
for len(stack) > 0 || node != nil {
// 将所有左子树节点入栈
for node != nil {
stack = append(stack, node)
node = node.Left
}
// 弹出栈顶元素，即当前最小节点
node = stack[len(stack)-1]
stack = stack[:len(stack)-1]
// 访问节点
k--
if k == 0 {
return node.Val
}
// 继续遍历右子树
node = node.Right
}
return 0
}
1
write your code here
相似题目
| 题目 | 难度 | 题解 |
|---|---|---|
| 二叉树的中序遍历 | Easy | |
| 二叉树中第二小的节点 | Easy |
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！