My code:
public class Solution {
private TreeNode kthNode = null;
private int count = 0;
public int kthSmallest(TreeNode root, int k) {
if (root == null)
return 0;
find(root, k);
return kthNode.val;
}
private void find(TreeNode root, int k) {
if (root.left != null)
find(root.left, k);
count++;
if (count == k) {
kthNode = root;
return;
}
if (root.right != null)
find(root.right, k);
}
}
My test result:
Paste_Image.png
还有个做法，是 Binary search
我的做法，复杂度是 O(n)
但是我感觉，下面这个做法，复杂度更高，因为他每次都需要统计下左子树个数。很多都是重复操作。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int kthSmallest(TreeNode root, int k) {
if (root == null)
return 0;
int leftSize = size(root.left);
if (k <= leftSize)
return kthSmallest(root.left, k);
else if (k > leftSize + 1)
return kthSmallest(root.right, k - leftSize - 1);
else
return root.val;
}
private int size(TreeNode root) {
if (root == null)
return 0;
return 1 + size(root.left) + size(root.right);
}
}
这道题目典型思路就是用 in-order 来做。
**
总结： in order tree
**
Anyway, Good luck, Richardo!
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int kthSmallest(TreeNode root, int k) {
if (root == null) {
return 0;
}
TreeNode curr = root;
Stack<TreeNode> st = new Stack<TreeNode>();
while (curr != null) {
st.push(curr);
curr = curr.left;
}
int counter = 0;
while (!st.isEmpty()) {
curr = st.pop();
counter++;
if (counter == k) {
return curr.val;
}
if (curr.right != null) {
curr = curr.right;
while (curr != null) {
st.push(curr);
curr = curr.left;
}
}
}
return -1;
}
}
题目里面说最优可以达到O(h),其实并不是那样。
首先有三种做法，
Inorder iteration, recursion + 计数器 就有两种
还有一种就是 divide and conquer
divide and conquer 代码如下：
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int kthSmallest(TreeNode root, int k) {
if (root == null) {
return -1;
}
TreeNode curr = root;
while (curr != null) {
int left = count(curr.left);
if (left < k - 1) {
k = k - left - 1;
curr = curr.right;
}
else if (left > k - 1) {
curr = curr.left;
}
else {
return curr.val;
}
}
return -1;
}
private int count(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + count(root.left) + count(root.right);
}
}
但是其实这种做法复杂度达到了 O(n log n)
所以题目中说到了，如果可以更改数据结构，让每个结点存的value是其左子树的结点个数，那么就可以 O(h) 实现了。
可惜的时候，题目给的输入没有这个特性。
这个复杂度也误导了很多人。
reference:
http://www.geeksforgeeks.org/find-k-th-smallest-element-in-bst-order-statistics-in-bst/
其实就是一道简单题。
Anyway, Good luck, Richardo! -- 09/07/2016
