230. Kth Smallest Element in a BST
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
**Note: ** You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
Example 1:
代码语言：javascript复制Input: root = [3,1,4,null,2], k = 1
3
/
1 4
2
Output: 1Example 2:
代码语言：javascript复制Input: root = [5,3,6,2,4,null,null,1], k = 3
5
/
3 6
/
2 4
/
1
Output: 3Follow 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?
思路：
由于bst的性质，所以bst的中序遍历，就是把bst从小到大输出，这样就能很容易找到第k小的数。
代码：
go：
代码语言：javascript复制/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func kthSmallest(root *TreeNode, k int) int {
stack := list.New()
cur := root
for stack.Len() != 0 || cur != nil{
if cur != nil {
stack.PushBack(cur)
cur = cur.Left
} else {
// visit
e := stack.Back()
stack.Remove(e)
cur = e.Value.(*TreeNode)
k--
if 0 == k {
return cur.Val
}
cur = cur.Right
}
}
return -1 // corner case
}
/*func kthSmallest(root *TreeNode, k int) int {
stack := []*TreeNode{}
t := root
for t != nil || len(stack) != 0 {
for t != nil {
stack = append(stack, t)
t = t.Left
}
t, stack = stack[len(stack)-1], stack[:len(stack)-1]
k--
if k == 0 {
return t.Val
}
t = t.Right
}
return -1
}*/
