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 的 max heap，一直有 insert 的时候好办；有 delete 而且删掉的 node 又在 heap 里就只好找一下 in order successor 了。
public class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
private TreeNode helper(int[] nums, int start, int end){
if(start > end) return null;
if(start == end) return new TreeNode(nums[start]);
int mid = start + (end - start) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, start, mid - 1);
root.right = helper(nums, mid + 1, end);
return root;
}
}
public class Solution {
public boolean verifyPreorder(int[] preorder) {
return helper(preorder, 0, preorder.length - 1);
}
private boolean helper(int[] preorder, int start, int end){
if(end - start <= 1) return true;
int breakPoint = start + 1;
int root = preorder[start];
// breakPoint should stop at index of first element > root
// if no left subtree, breakPoint stops at start;
for(int i = start + 1; i <= end; i++){
if(preorder[i] < root) breakPoint ++;
else break;
}
for(int i = breakPoint; i <= end; i++){
if(preorder[i] < root) return false;
}
return helper(preorder, start + 1, breakPoint - 1)
&& helper(preorder, breakPoint, end);
}
}
public class Solution {
public void recoverTree(TreeNode root) {
List<TreeNode> list = new ArrayList<TreeNode>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
list.add(node);
cur = node.right;
}
if(list.size() == 2){
swap(list.get(0), list.get(1));
return;
}
TreeNode p = null;
TreeNode q = null;
for(int i = 1; i < list.size(); i++){
if(list.get(i).val < list.get(i - 1).val){
p = list.get(i - 1);
break;
}
}
for(int i = list.size() - 2; i >= 0; i--){
if(list.get(i + 1).val > list.get(i).val){
q = list.get(i + 1);
break;
}
}
swap(p, q);
return;
}
private void swap(TreeNode p, TreeNode q){
if(p == null || q == null) return;
int temp = p.val;
p.val = q.val;
q.val = temp;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public void recoverTree(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
TreeNode p = null;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
if(p == null){
p = node;
} else {
if(node.val < p.val){
break;
} else {
p = node;
}
}
cur = node.right;
}
stack.clear();
cur = root;
TreeNode q = null;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.right;
}
TreeNode node = stack.pop();
if(q == null){
q = node;
} else {
if(node.val > q.val){
break;
} else {
q = node;
}
}
cur = node.left;
}
swap(p, q);
return;
}
private void swap(TreeNode p, TreeNode q){
if(p == null || q == null) return;
int temp = p.val;
p.val = q.val;
q.val = temp;
}
}
public void recoverTree(TreeNode root) {
//use inorder traversal to detect incorrect node
inOrder(root);
int temp = first.val;
first.val = second.val;
second.val = temp;
}
TreeNode prev = null;
TreeNode first = null;
TreeNode second = null;
public void inOrder(TreeNode root){
if(root == null) return;
//search left tree
inOrder(root.left);
//in inorder traversal of BST, prev should always have smaller value than current value
if(prev != null && prev.val >= root.val){
//incorrect smaller node is always found as prev node
if(first == null) first = prev;
//incorrect larger node is always found as curr(root) node
second = root;
}
//update prev node
prev = root;
//search right tree
inOrder(root.right);
}