描述
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:
1 | Input: root = [3,1,4,null,2], k = 1 |
Example 2:
1 | Input: root = [5,3,6,2,4,null,null,1], k = 3 |
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(Java)
1 | /** |