给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 1

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3        5       / \      3   6     / \    2   4   /  1 输出: 3

答案：

 1public int kthSmallest(TreeNode root, int k) {
 2    ArrayList<Integer> buffer = new ArrayList<Integer>();
 3    inorderSearch(root, buffer, k);
 4    return buffer.get(k - 1);
 5}
 6
 7public void inorderSearch(TreeNode node, ArrayList<Integer> buffer, int k) {
 8    if (buffer.size() >= k)
 9        return;
10    if (node.left != null) {
11        inorderSearch(node.left, buffer, k);
12    }
13    buffer.add(node.val);
14    if (node.right != null) {
15        inorderSearch(node.right, buffer, k);
16    }
17}

解析:

首先我们要明白什么是二叉搜索树，二叉搜索树的定义是，若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。知道二叉搜索树的定义，上面代码就很容易理解了。他的写法就是DFS，先把最小的节点放到list中，然后是倒数第二小的……，直到第k个，也就是第k个最小的元素。我们再来看一个非递归的写法

 1public int kthSmallest(TreeNode root, int k) {
 2    Stack<TreeNode> stack = new Stack<TreeNode>();
 3    TreeNode p = root;
 4    int count = 0;
 5
 6    while (!stack.isEmpty() || p != null) {
 7        if (p != null) {
 8            stack.push(p);
 9            p = p.left;
10        } else {
11            TreeNode node = stack.pop();
12            if (++count == k)
13                return node.val;
14            p = node.right;
15        }
16    }
17    return Integer.MIN_VALUE;
18}

这题比较简单，解法也比较多，我们再来看一种写法，

 1int count = 0;
 2int result = Integer.MIN_VALUE;
 3
 4public int kthSmallest(TreeNode root, int k) {
 5    traverse(root, k);
 6    return result;
 7}
 8
 9public void traverse(TreeNode root, int k) {
10    if (root == null)
11        return;
12    traverse(root.left, k);
13    count++;
14    if (count == k) {
15        result = root.val;
16        return;
17    }
18    traverse(root.right, k);
19}

这种解法也比较简单，也很好理解，下面我们再来看一种解法

 1public int kthSmallest(TreeNode root, int k) {
 2    Stack<TreeNode> st = new Stack<>();
 3    while (root != null) {
 4        st.push(root);
 5        root = root.left;
 6    }
 7    while (k != 0) {
 8        TreeNode n = st.pop();
 9        k--;
10        if (k == 0)
11            return n.val;
12        TreeNode right = n.right;
13        while (right != null) {
14            st.push(right);
15            right = right.left;
16        }
17    }
18    return -1;
19}

这种解法也比较经典，第8行每次pop的都是最小的，如果能看明白这个就比较简单了，再来看一种解法

 1private static int number = 0;
 2private static int count = 0;
 3
 4public int kthSmallest(TreeNode root, int k) {
 5    count = k;
 6    helper(root);
 7    return number;
 8}
 9
10public void helper(TreeNode n) {
11    if (n.left != null)
12        helper(n.left);
13    count--;
14    if (count == 0) {
15        number = n.val;
16        return;
17    }
18    if (n.right != null)
19        helper(n.right);
20}

这个就不说了，和上面第3中很像，我们来看最后一种解法。

 1public int kthSmallest(TreeNode root, int k) {
 2    int count = countNodes(root.left);
 3    if (k <= count) {
 4        return kthSmallest(root.left, k);
 5    } else if (k > count + 1) {
 6        return kthSmallest(root.right, k - 1 - count);
 7    }
 8    return root.val;
 9}
10
11public int countNodes(TreeNode n) {//计算节点个数
12    if (n == null)
13        return 0;
14    return 1 + countNodes(n.left) + countNodes(n.right);
15}