?LeetCode刷題實(shí)戰(zhàn)230：二叉搜索樹(shù)中第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);
    }
}