二叉搜索树中第K小的元素

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst

题目描述:

给定一个二叉搜索树的根节点 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

题目分析:

1. 求二叉搜索树所有元素中第k小大数

思路:

• 使用中序遍历拿到二叉树的所有元素
• 中序遍历本身有序,因此无需再对拿到大元素进行排序,直接返回第k个元素即可.

代码实现:

class Solution {
    public List<Integer> list = new ArrayList();
    public int kthSmallest(TreeNode root, int k) {
      dfs(root);
      // 索引从0开始.
      return list.get(--k);
    }
    public void dfs(TreeNode root) {
        // 中序遍历.
        if (root == null) return;
        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
    }
}