进阶: 如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化 kthSmallest 函数?
解答
想到的方法一,是变成数组,然后用小顶堆或者快速搜索。
方法二就是中序遍历,数k个。
classSolution:defkthSmallest(self,root: TreeNode,k:int)->int: stack =[] p = root count =0while p isnotNoneor stack:while p isnotNone: stack.append(p) p = p.left p = stack.pop() count +=1if count == k:return p.val p = p.right
Runtime: 48 ms, faster than 95.99% of Python3 online submissions for Kth Smallest Element in a BST.
Memory Usage: 16.6 MB, less than 98.18% of Python3 online submissions for Kth Smallest Element in a BST.
Runtime: 56 ms, faster than 98.94% of JavaScript online submissions for Kth Smallest Element in a BST.
Memory Usage: 39.4 MB, less than 63.64% of JavaScript online submissions for Kth Smallest Element in a BST.
Runtime: 12 ms, faster than 70.69% of Go online submissions for Kth Smallest Element in a BST.
Memory Usage: 5.8 MB, less than 10.00% of Go online submissions for Kth Smallest Element in a BST.
var kthSmallest = function(root, k) {
const stack = []
let p = root
let count = 0
while (p || stack) {
while (p) {
stack.push(p)
p = p.left
}
p = stack.pop()
count++
if (count === k) {
return p.val
}
p = p.right
}
};
func kthSmallest(root *TreeNode, k int) int {
stack := []*TreeNode{}
count := 0
p := root
for p != nil || len(stack) != 0 {
for p != nil {
stack = append(stack, p)
p = p.Left
}
p = stack[len(stack)-1]
stack = stack[:len(stack)-1]
count++
fmt.Println("count", count)
if count == k {
return p.Val
}
p = p.Right
}
return -1
}