class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || p == root || q == root){
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // if(left != null){
        //     return left;
        // }

        // if(right != null){
        //     return right;
        // }
        if(left == null){
            return right;
        }

        if(right == null){
            return left;
        }

        if(left != null && right != null){
            return root;
        }

        return null;
    }
}  

这两种写法覆盖的条件不一样，第一种情况，无法满足所有case

// if(left != null){

// return left;

// }

// if(right != null){

// return right;

// }

if(left == null){

return right;

}

if(right == null){

return left;

}

经典题：top K

//由于找第 K 大元素，其实就是整个数组排序以后后半部分最小的那个元素。因此，我们可以维护一个有 K 个元素的最小heap

// 只要当前遍历的元素比堆顶元素大， 堆顶弹出，遍历的元素进去 (堆这种数据具有内部shiftup , shiftdown 功能，自己维持最小堆。Java默认的是最小堆。)

 class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(nums.length == 0) return -1;
        int res = minHeap(nums, k);
        return res;
    }

    //最小堆
    private int minHeap(int[] nums, int k){
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i = 0; i < k; i++){
            pq.offer(nums[i]);
        }

        for(int i = k; i < nums.length; i++){
            if(nums[i] > pq.peek()){
                pq.poll();//需要先弹出
                pq.offer(nums[i]);
            }
        }
        return pq.peek();
    }
}  

 class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(nums.length == 0) return -1;
        int start = 0;
        int end = nums.length - 1;
        while(true){
            int goal = quickSort(nums, start, end);
            if(goal == nums.length - k){
                return nums[goal];
            
            }else if(goal > nums.length - k){
                end = goal - 1; //更新
            }else{
                start = goal + 1;//更新
            }
        }
    }

    private int quickSort(int[] nums, int start, int end){
        int i = start;
        int j = end;
        int flag = nums[start];
        while(i < j){
            while(i < j && nums[j] >= flag){
                j--;
            }
            while(i < j && nums[i] <= flag){
                i++;
            }
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        nums[start] = nums[i];
        nums[i] = flag;
        return i;
    }

  
}  

这里需要优化一下，加入一个洗牌的算法：

Random random = new Random ();

// 在区间随机选择一个元素作为

if (start > end) {

int randomIndex = 1 + random. nextInt (end); //包含0 不包含end, 为了不是0， 加一个1；

swap (nums, start, randomIndex);

}