230. Kth Smallest Element in a BST

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.

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?

题目大意

找二叉搜索树中,第 k 个小的值。

解题思路

通过辅助栈,按照中序遍历二叉树。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
var tree = root
var stack = [TreeNode?]()
while tree != nil {
stack.append(tree)
tree = tree?.left
}
var num = 1
while !stack.isEmpty && num <= k {
tree = stack.removeLast()
num += 1
var r = tree?.right
while r != nil {
stack.append(r)
r = r?.left
}
}
return tree?.val ?? 0
}
}
0%