LeetCode刷题实战230：二叉搜索树中第K小的元素-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 二叉搜索树中第K小的元素，我们先来看题面：

https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/

Given the root of a binary search tree, and an integer k, return the kth (1-indexed) smallest element in the tree.

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

示例

解题

一看到求第K小的问题，应该会容易想到建立大顶堆来做，但是如果这道题采用大顶堆的方式来做的话，是比较麻烦的，还得转换为数组，这样的话就完全忽视了二叉搜索树本身的特点。

为了利用二叉搜索树的特点，一种可以采取的方法就是对二叉搜索树进行中序遍历，遍历结果必定是个升序数组，当数组长度达到k时，那么数组末尾的元素就是二叉搜索树的第K小元素了。不过这样的话就需要一个大小为O(K)的开辟辅助空间。

为了既利用二叉搜索树的特点，又能减少辅助空间的开销，可以直接对左子树结点进行计数，如果左子树的结点数等于k-1的话，说明当前结点就是第k小的结点了；如果左子树结点数小于k-1的话，说明第k小的结点在当前结点的右边，假设左子树上的结点有num个，那么此时就递归查找右子树上第k-1-num小的元素；如果左子树结点大于k-1的话，说明第k小的结点就在左子树上，那么就递归查找左子树上第k小的元素。

中序遍历方法

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

使用递归（计算节点数量）：

class Solution { 
    public int count(TreeNode root){
        if(root == null)
            return 0;
        return 1 + count(root.left) + count(root.right);
    }
    public int kthSmallest(TreeNode root, int k) {
        int num = count(root.left);
        if(num == k-1)
            return root.val;
        if(num > k-1)
            return kthSmallest(root.left,k);
        return kthSmallest(root.right,k - num-1);
    }
}