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?
Solution1：二分查找
思路：在当前结点，数左子树的结点总数num，(1)如果不到k - 1，说明在右子树里面；(2)如果等于k-1，当前结点就是kthSmallest；(3)如果大于k-1,说明就在左子树里面，递归继续在左子树里面找(k-num-1)thSmallest，不用管右子树了。
时间复杂度: 如果一直是情况(3)，就是O(N)，如果一直是情况(1)必然是O(N^2)，
Average: 当是树是基本平衡的时候，T(N) = T(N / 2) + O(N/2) => O(N)
worst: O(N ^ 2) 比如只有左子树，target还在最左下
Time Complexity: O(N) Space Complexity: O(N)
Solution2.a：二分查找 + augmented TreeNode data structure
(不如2.b)
思路：将结点的结构多加一个lCount，记录sub_left_tree的结点总数。
这样在每次调用kthSmallest()时，不用每次再count，直接看lCount二分就能找到，是O(logN)。
但是这是在新树已经建立好的情况下，如果是按题目的话建立树的过程这里对整体树复制，因为用Iterative由上倒下count需要O(logN)，整体也还是需要O(NlogN)；如果是从的数组建立的话，排序O(NlogN) + 累积Count(O(N)) + 建树O(N)
2.b 思路与a大体相同，count_all_sub 和 count_left_sub是一样的。用分治法建树只需要O(N)，由低向上count
Solution3.a：In-order Traversal (recursive)
Time Complexity: O(k), worst case O(N) Space Complexity: O(N) 递归缓存
Solution3.b：In-order Traversal (iterative)
Time Complexity: O(k) worst case O(N) Space Complexity: O(N)
Solution1 Code：
class Solution {
public int kthSmallest(TreeNode root, int k) {
int left_count = countSubTree(root.left);
if(left_count == k - 1) {
return root.val;
}
else if(left_count > k - 1) {
// kthSmallest element in the left tree
return kthSmallest(root.left, k);
}
else {
// kthSmallest element in the right tree
return kthSmallest(root.right, k - left_count - 1);
}
}
private int countSubTree(TreeNode root) {
if(root == null) return 0;
return countSubTree(root.left) + countSubTree(root.right) + 1;
}
}
Solution2 Code：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class TreeNodeWithCount {
int val;
int lCount;
TreeNodeWithCount left;
TreeNodeWithCount right;
TreeNodeWithCount(int x) { val = x; }
}
public class Solution {
public int kthSmallest(TreeNode root, int k) {
if(root == null) return -1;
TreeNodeWithCount rootWithCount = createBSTWithCount(root);
return kthSmallestWithCount(rootWithCount, k);
}
public TreeNodeWithCount createBSTWithCount(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
TreeNodeWithCount rootWithCount = null;
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNodeWithCount nodeWithCount = new TreeNodeWithCount(node.val);
rootWithCount = insertBSTWithCount(rootWithCount, nodeWithCount);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
return rootWithCount;
}
public TreeNodeWithCount insertBSTWithCount(TreeNodeWithCount rootWithCount, TreeNodeWithCount nodeWithCount) {
TreeNodeWithCount cur = rootWithCount, parent = rootWithCount;
while(cur != null) {
parent = cur;
if(nodeWithCount.val < cur.val) {
cur.lCount++;
cur = cur.left;
} else {
cur = cur.right;
}
}
if(rootWithCount == null) {
rootWithCount = nodeWithCount;
} else if(nodeWithCount.val < parent.val) {
parent.left = nodeWithCount;
} else {
parent.right = nodeWithCount;
}
return rootWithCount;
}
public int kthSmallestWithCount(TreeNodeWithCount rootWithCount, int k) {
while(rootWithCount != null) {
if(k == rootWithCount.lCount + 1) {
return rootWithCount.val;
} else if(k <= rootWithCount.lCount) {
rootWithCount = rootWithCount.left;
} else {
k = k - rootWithCount.lCount - 1;
rootWithCount = rootWithCount.right;
}
}
return -1;
}
}
Solution2.b Code：
public class Solution {
public int kthSmallest(TreeNode root, int k) {
TreeNodeWithCount rootWithCount = buildTreeWithCount(root);
return kthSmallest(rootWithCount, k);
}
private TreeNodeWithCount buildTreeWithCount(TreeNode root) {
if (root == null) return null;
TreeNodeWithCount rootWithCount = new TreeNodeWithCount(root.val);
rootWithCount.left = buildTreeWithCount(root.left);
rootWithCount.right = buildTreeWithCount(root.right);
if (rootWithCount.left != null) rootWithCount.count += rootWithCount.left.count;
if (rootWithCount.right != null) rootWithCount.count += rootWithCount.right.count;
return rootWithCount;
}
private int kthSmallest(TreeNodeWithCount rootWithCount, int k) {
if (k <= 0 || k > rootWithCount.count) return -1;
if (rootWithCount.left != null) {
if (rootWithCount.left.count >= k) return kthSmallest(rootWithCount.left, k);
if (rootWithCount.left.count == k-1) return rootWithCount.val;
return kthSmallest(rootWithCount.right, k-1-rootWithCount.left.count);
} else {
if (k == 1) return rootWithCount.val;
return kthSmallest(rootWithCount.right, k-1);
}
}
class TreeNodeWithCount {
int val;
int count;
TreeNodeWithCount left;
TreeNodeWithCount right;
TreeNodeWithCount(int x) {val = x; count = 1;};
}
}
Solution3.a Code：
class Solution {
private int result;
private int count;
public int kthSmallest(TreeNode root, int k) {
count = k;
helper(root);
return result;
}
public void helper(TreeNode node) {
if(node == null) return;
helper(node.left);
count--;
if (count == 0) {
result = node.val;
return;
}
helper(node.right);
}
}
Solution3.a.2 Round1 Code：
class Solution {
public int kthSmallest(TreeNode root, int k) {
TreeNode result = dfs(root, k);
if(result == null) return 0;
else return result.val;
}
private int count = 0;
private TreeNode dfs(TreeNode root, int k) {
if(root == null) return null;
TreeNode l_res = dfs(root.left, k);
if(l_res != null) return l_res;
count++;
if(count == k) return root;
TreeNode r_res = dfs(root.right, k);
if(r_res != null) return r_res;
return null;
}
}
Solution3.b Code：
class Solution {
public int kthSmallest(TreeNode root, int k) {
int count = k;
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<>();
while(cur != null || !stack.empty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
count--;
if(count == 0) return cur.val;
cur = cur.right;
}
return Integer.MIN_VALUE; //not found
}
}
