给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

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

解题思路

二叉搜索树的中序遍历是升序序列。

先往左边查找，用一个栈保存节点，一直查找到没有左边节点为止，弹栈检查是否到第k个了，如果还没到就转向弹栈元素的右边子树继续查找

也可以用递归解法，但缺点是必须中序遍历完整个树，然后取第 k 个元素

Java实现

迭代解法

public int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()){
        while (curr != null){
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        k--;
        if (k == 0){
            return curr.val;
        }
        curr = curr.right;
    }
    return -1;
}

递归解法

class Solution {
    List<Integer> list = new ArrayList();
    public int kthSmallest(TreeNode root, int k) {
        inOrder(root, k);
        return list.get(k-1);
    }
    private void inOrder(TreeNode root, int k){
        if (root == null || list.size() == k){
            return;
        }
        inOrder(root.left, k);
        list.add(root.val);
        inOrder(root.right, k);
    }
}