【LeetCode】Day90-二叉搜索树中第K小的元素

题目

230. 二叉搜索树中第K小的元素【中等】

题解

中序遍历

二叉搜索树中序遍历就是一个递增数列，因此第K小的元素即二叉搜索树中序遍历的第K个结点的值，用中序遍历就可以解决~

class Solution {
    
    int count=0,res=0;
    public int kthSmallest(TreeNode root, int k) {
    
        midOrder(root,k);
        return res;
    }
    public void midOrder(TreeNode root,int k){
    
        if(root==null)
            return;
        midOrder(root.left,k);
        count++;
        if(count==k){
    
            res=root.val;
            return;
        }
        midOrder(root.right,k);
    }
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$

p.s 期末终于结束了！以后再也不用上课啦！不过在家的效率真是一言难尽，又5天没更了，要是在学校的话估计早就突破100天了