230. 二叉搜索树中第 k 小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 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 小的元素

/**
 * 利用二叉搜索树的中序遍历结果是一个升序序列的特性，从中序遍历序列中获取
 * @param root
 * @param k
 * @return
 */
public int kthSmallest(TreeNode root, int k) {
    List<Integer> valList = new ArrayList<>();
    inOrder(root, valList);
    return valList.get(k - 1);
}
/**
 * 二叉搜索树的中序遍历结果是一个升序序列
 *
 * @param node
 * @param valList
 */
private void inOrder(TreeNode node, List<Integer> valList) {
    if (node == null) {
        return;
    }
    inOrder(node.left, valList);
    valList.add(node.val);
    inOrder(node.right,valList);
}