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

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

思路

中序遍历该二叉搜索树，放到list，list里面是从小到大，索引从0开始，返回k-1上的数

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

更优写法

class Solution {
    
    private int c;
    private TreeNode temp;
    public int kthSmallest(TreeNode root, int k) {
        c=0;
        
        inorder(k,root);
        
        return temp.val;
    }
    
    void inorder(int k,TreeNode root){
        
        if(root==null){
            return ;
        }
        
        inorder(k,root.left);
        c++;
        if(k==c){
            temp=root;
        }
        inorder(k,root.right);
        
    }
}