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.
这题是看到98. Validate Binary Search Tree 的一个非常好的summary里面这样写的。对于k的边界，考虑极端的，k=1就比较容易确定了。
DFS in-order iterative:
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
k--;
if (k == 0) return root.val;
root = root.right;
}
return -1;
}
因为是inorder traverse，这么看，时间复杂度是O(n)。
这题还有其他两种方法，明天写。
Mar 26
微风习习阳光和煦的周日。开始。
刚才百度了一下，dfs跟递归其实是不是一回事。dfs>递归，递归是dfs的一种手段，比如上面的stack就是非递归的、iterative 的dfs。
DFS in-order recursive
试着写了一下DFS in-order recursive，很接近答案了，尤其覃超说的 inoder就把递归放前后，中间写东西。所以把
count--;
if (count == 0) {
res = root.val;
}
这段放中间。我犯的错误是，recursion函数中又带上了k这个参数，导致count--又带入了recursion。
略微修改后的AC代码：
public class Solution {
int res, count;
public int kthSmallest(TreeNode root, int k) {
count = k;
recursion(root);
return res;
}
private void recursion(TreeNode root) {
if (root == null) return;
recursion(root.left);
count--;
if (count == 0) {
res = root.val;
}
recursion(root.right);
}
}
这种的时间复杂度不知该怎么分析。。感觉是O(n)呢。空间复杂度是栈的复杂度，大概也是O(n)吧。
Binary Search (dfs): most preferable
最后一种也是复杂度最优的方法（讲解可以参考：http://blog.csdn.net/sunao2002002/article/details/46726245），非常容易懂。
首先计算左子树node的个数left
- 若left + 1 == k ，则root.val就是kth smallest
- 若left + 1 > k ， 则kth smallest在左子树中
- 若left + 1 < k ，则转换为在右子树中，寻找第K-left-1（去除左子树和root node）个元素。
时间复杂度O(logn)。
public int kthSmallest(TreeNode root, int k) {
int left = countNode(root.left);
if(left + 1 == k ) return root.val ;
else if(left + 1 > k ) return kthSmallest(root.left , k);
else return kthSmallest(root.right , k - left - 1);
}
private int countNode(TreeNode root) {
//这里return 的应该是0 。用root只有一个node的情形考虑就行了。
if (root == null) return 0;
return 1 + countNode(root.left) + countNode(root.right);
}
这代码一次AC了，有点开心。
