算法通关村第九关-白银挑战二分查找与高频搜索树

大家好我是苏麟,今天看看二分查找相关的题目 .

二分查找拓展问题

山脉数组的峰顶索引

描述 :

符合下列属性的数组 arr 称为 山脉数组 ：

• arr.length >= 3
• 存在 i（0 < i < arr.length - 1）使得：
  arr[0] < arr[1] < … arr[i-1] < arr[i]
  arr[i] > arr[i+1] > … > arr[arr.length - 1]

给你由整数组成的山脉数组 arr ，返回满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i

题目 :

LeetCode 852. 山脉数组的峰顶索引

852.山脉数组的封顶索引

分析 :

这个题其实就是前面找最小值的相关过程而已，最简单的方式是对数组进行一次遍历。

解析 :

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int length = arr.length;
        int n = 0;
        for(int i = 0; i< length - 1;i++){
            if(arr[i] > arr[i + 1]){
                n = i;
                break;
            }
        }
        return n;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

分析 :

使用二分来优化一下

因为此题是必为高峰数组 , 所以数组长度为 时下标1为最大值 .

解析 :

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int length = arr.length;
        if(length == 3){
            return 1;
        }
        int left = 1;
        int right = length - 1;
        while(left < right){
            int mid = (left + right) >>> 1;
            if(arr[mid - 1] < arr[mid] && arr[mid] < arr[mid + 1]){
                left = mid;
            }
            if(arr[mid - 1] > arr[mid] && arr[mid] > arr[mid + 1]){
                right = mid;
            }
            if(arr[mid - 1] < arr[mid] && arr[mid] > arr[mid + 1]){
                return mid;
            }
        }
        return left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

寻找旋转排序数组中的最小值

描述 :

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]]

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

题目 :

LeetCode 153. 寻找旋转排序数组中的最小值 :

153.寻找旋转排序数组中的最小值

分析 :

一个不包含重复元素的升序数组在经过旋转之后，可以得到下面可视化的折线图：

其中横轴表示数组元素的下标，纵轴表示数组元素的值。图中标出了最小值的位置，是我们需要查找的目标。

我们考虑数组中的最后一个元素 xxx ：

在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于 xxx；
而在最小值左侧的元素，它们的值一定都严格大于 xxx。
因此，我们可以根据这一条性质，通过二分查找的方法找出最小值。

在二分查找的每一步中，左边界为 left，右边界为 right，区间的中点为 mid，最小值就在该区间内。我们将中轴元素 nums[mid] 与右边界元素 nums[right] 进行比较，可能会有以下的三种情况：

第一种情况是 nums[mid] > nums[right]。如下图所示，这说明 nums[mid] 是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分。

第二种情况是nums[mid] > nums[right]。如下图所示，这说明 nums[mid] 是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分。

由于数组不包含重复元素，并且只要当前的区间长度不为 1，mid 就不会与 right 重合；而如果当前的区间长度为 1，这说明我们已经可以结束二分查找了。因此不会存在nums[mid] = nums[right]的情况。

当二分查找结束时，我们就得到了最小值所在的位置。

解析 :

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int mid = (left + right) >>> 1;
            if(nums[mid] > nums[right]){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return nums[left];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

中序与搜索树

在前面我们发现很多题使用前序、后序或者层次遍历都可以解决，但几乎没有中序遍历的。这是因为中序与前后序相比有不一样的特征，例如中序可以和搜索树结合在一起，但是前后序则不行。

二叉搜索树是一个很简单的概念，但是想说清楚却不太容易。简单来说就是如果一棵二叉树是搜索树，则按照中序遍历其序列正好是一个递增序列。比较规范的定义是:

• 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值;
• 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值;
• 它的左、右子树也分别为二又排序树。下面这两棵树一个中序序列是 {3.6.9,10,14,16,19}，一个是{3,6,9,10}，因此都是搜索树:
  
  搜索树的题目虽然也是用递归，但是与前后序有很大区别，主要是因为搜索树是有序的，就可以根据条件决定某些递归就不必执行了，这也称为“剪枝”。

二叉搜索树中的搜索

描述 :

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

题目 :

LeetCode 700. 二叉搜索树中的搜索

700.二叉搜索树中的搜索

分析 :

本题看起来很复杂，但是实现非常简单，递归:

• 如果根节点为空 root == null 或者根节点的值等于搜索值 val == root.val，返回根节点
• 如果 val < root.val，进入根节点的左子树查找 searchBST(root.left, val)
• 如果 val > root.val，进入根节点的右子树查找 searchBST(root.right, val)

解析 :

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        return searchNode(root,val);
    }
    public TreeNode searchNode(TreeNode root,int val){
        if(root == null){
           return null;
        }
        if(root.val == val){
            return root;
        }else{
            if(val < root.val){
               root = searchBST(root.left,val);
            }else{
                root =searchBST(root.right,val);
            }
        }
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

分析 :

迭代方式也很简单 , 只要值不相等就循环 , 循环到最后还没有就返回null .

解析 :

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while(root != null && root.val != val){
           root = root.val > val ? root.left : root.right;
        }
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

验证二叉搜索树

描述 :

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数
• 节点的右子树只包含 大于 当前节点的数
• 所有左子树和右子树自身必须也是二叉搜索树

题目 :

LeetCode 98. 验证二叉搜索树

验证二叉搜索树

分析 :

我们就以这个为例 :

以此代码为例讲解 :

class Solution {
    public boolean isValidBST(TreeNode root) {
        return is(root);
    }

    long pre = Long.MIN_VALUE;
    public boolean is(TreeNode root){
        if(root == null){
            return true;
        }
        if(root.val <= pre){
            return false;
        }
        pre = root.val;
        return is(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

第一步 :

定义变量 : long pre = Long.MIN_VALUE; 他的值为 -9223372036854775808 远远比 1 小 用来比较

第二步 :

用pre 和 root.val 比较 如果小于就返回false 否则就把root.val赋值给 pre , 最后传入节点root.right

第三步 :

以 root.right 为根节点继续比较

而下面这个代码是 递归左节点的 , 如果根节点的左节点不是二叉搜索树返回false

       if(!is(root.left)){
            return false;
        }
1
2
3

解析 :

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return is(root);
    }

    long pre = Long.MIN_VALUE;
    public boolean is(TreeNode root){
        if(root == null){
            return true;
        }
        if(!is(root.left)){
            return false;
        }
        if(root.val <= pre){
            return false;
        }
        pre = root.val;
        return is(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

这期就到这里了 , 下期见!