0%

二叉搜索树种第k小元素

1
2
3
4
5
6
7
二叉搜索树定义

对于每个节点的值,该值比左节点的值大,比右节点小

二叉搜索树中序遍历

二叉搜索树的中序遍历,就是树种元素从小到大的遍历顺序

【题目】

给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素

【难度】

★★☆☆

【解答】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func kthSmallest(root *TreeNode, k int) int {
result := int(math.MaxInt32)
sub(root, &k, &result)
return result
}

func sub(node *TreeNode, k *int, result *int) {
if node == nil || *result != int(math.MaxInt32) {
return
}

sub(node.Left, k, result)
if *k == 1 {
*result = node.Val
}
*k--
sub(node.Right, k, result)
}