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小元素。
followup:如果这个二叉树经常改变(增删),然后又会经常查第k小元素,该怎么优化?
1、暴力的思路:把二叉搜索树转为一个有序数组,返回数组第k-1个元素。要遍历所有树节点,时间复杂度O(n);要用一个数组存储,空间复杂度O(n)。
2、先找到最小元素,通过栈存储父节点,利用前序遍历找到第k个。
public int kthSmallest(TreeNode root, int k) {
//1 bst转为有序数组,返回第k个,时间 O(n), 空间 O(n)
//2 先找到bst中最小的叶子节点,然后递归向上搜索第k个,父节点存储在栈中
Stack<TreeNode> stack = new Stack<>();
TreeNode dummy = root;
while (dummy != null) {
stack.push(dummy);
dummy = dummy.left;
}
while (k > 1) {
TreeNode top = stack.pop();
dummy = top.right;
while (dummy != null) {
stack.push(dummy);
dummy = dummy.left;
}
k--;
}
return stack.peek().val;
}