p230

 


 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class  {
    public int kthSmallest(TreeNode root, int k) {

		int ans = 0;
		TreeNode knode = root;

		int c = count(knode.left);
		if (c + 1 == k)
			return knode.val;

		if (c < k)
			return kthSmallest(knode.right, k - 1 - c);// 往右的差值
		if (c + 1 > k)
			return kthSmallest(knode.left, k);

		return ans;
	}

	public int count(TreeNode root) {

		if (root == null)
			return 0;

		return 1 + count(root.left) + count(root.right);
	}
}