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