思维导图

预备知识：二分查找基础知识

已知一个排序数组A，如 A=[-1，2，5，20，90，100，207，800]
另外一个乱序数组B，如 B=[50，90，3，-1，207，8]
求B中的任意某个元素，是否在A中出现，结果存储在数组C中，出现用1代表，未出现用0代表，如 C=[0，1，0，1，1，0]

表中元素升序排列，将表中间位置的关键字与查找关键字比较：
1、如果两者相等，则查找成功；
2、否则利用中间位置将表分成前、后两个子表：
① 如果中间位置的关键字大于查找关键字，则进一步查找前一子表
② 否则进一步查找后一子表
重复以上过程，直到查找成功，或子表不存在为止。

• 二分查找（递归实现）

#include <vector>

bool binary_search(std::veator<int>&sort_array,
                int begin,int end,int target){
    if begin > end
        return false; 
    int mid=(begin + end）/2; 
    if(target == sort_array[mid])
        return true;
    else if (target < sort_array[mid])
        return binary_search(sort_array,begin,mid-1,target);
    else if (target > sort_array[mid])
        return binary_search(sort_array,mid+1,end,target);
}

• 二分查找（循环实现）

bool binary_search (std:: vector<int> & sort_array, int target){
    int begin =0; 
    int end = sort_array.size()-1; 
    while(begin <= end){
        int mid = (begin + end) /2; 
        if (target == sort_array [mid])
            return true;
        else if (target < sort_array [mid]) 
            end = mid-1; 
        else if (target > sort_array [mid])
            begin = mid +1; 
    }
    return false;
}

例1：插入位置（★）（二分查找）

给定一个排序数组nums（无重复元素）与目标值target，如果target在nums里出现，则返回下标；如果target在nums里未出现，则返回应该插入的下标，使得数组仍有序。

• LeetCode 35.Search Insert Position

#include <stdio.h>
#include <vector>

class Solution {
public:
    int searchInsert(std::vector<int>& nums, int target) {
        int index = -1,begin = 0,end = nums.size() - 1;
        while (index == -1){
            int mid = (begin + end) / 2;
            if (target == nums[mid]){
                index = mid;
            }
            else if (target < nums[mid]){
                if (mid == 0 || target > nums[mid - 1]){ //数组中没有target 
                    index = mid;
                }
                end = mid - 1;
            }
            else if (target > nums[mid]){
                if (mid == nums.size() - 1 || target < nums[mid + 1]){ //数组中没有target 
                    index = mid + 1;
                }
                begin = mid + 1;
            }
        }
        return index;
    }
};

int main(){
    int test[] = {1, 3, 5, 6};
    std::vector<int> nums;
    Solution solve;
    for (int i = 0; i < 4; i++){
        nums.push_back(test[i]);
    }
    for (int i = 0; i < 8; i++){
        printf("i = %d index = %d\n", i, solve.searchInsert(nums, i));
    }
    return 0;
}

例2：区间查找（★★）（二分查找）

给定一个排序数组nums（有重复元素）与目标值target，如果target在nums里出现，则返回所在区间的左右端点下标；如果target在nums里未出现，则返回 [-1，-1]。

• LeetCode 34.Search for a Range

#include <stdio.h>
#include <vector>

int left_bound(std::vector<int>& nums, int target){
    int begin = 0;
    int end = nums.size() - 1;
    while(begin <= end){
        int mid = (begin + end) / 2;
        if (target == nums[mid]){
            if (mid == 0 || nums[mid -1] < target){ //target未在数组中 
                return mid;  
            }
            end = mid - 1;
        }
        else if (target < nums[mid]){ //左边 
            end = mid - 1;
        }
        else if (target > nums[mid]){ //右边 
            begin = mid + 1;
        }
    }
    return -1;
}

int right_bound(std::vector<int>& nums, int target){
    int begin = 0;
    int end = nums.size() - 1;
    while(begin <= end){
        int mid = (begin + end) / 2;
        if (target == nums[mid]){
            if (mid == nums.size() - 1 || nums[mid + 1] > target){ //target未在数组中 
                return mid;
            }
            begin = mid + 1;
        }
        else if (target < nums[mid]){ //左边 
            end = mid - 1;
        }
        else if (target > nums[mid]){ //右边 
            begin = mid + 1;
        }
    }
    return -1;
}

class Solution {
public:
    std::vector<int> searchRange(std::vector<int>& nums, int target) {
        std::vector<int> result;
        result.push_back(left_bound(nums, target));
        result.push_back(right_bound(nums, target));
        return result;
    }
};

int main(){
    int test[] = {5, 7, 7, 8, 8, 8, 8, 10};
    std::vector<int> nums;
    Solution solve;
    for (int i = 0; i < 8; i++){
        nums.push_back(test[i]);
    }
    for (int i = 0; i < 12; i++){
        std::vector<int> result = solve.searchRange(nums, i);
        printf("%d : [%d, %d]\n",i , result[0], result[1]);
    }
    return 0;
}

例3：旋转数组查找（★★）（二分查找）

给定一个排序数组nums（无重复元素），且nums可能以某个未知下标旋转。给定目标值target，求target是否在nums中出现，若出现返回所在下标，未出现返回-1。

• LeetCode 33.Search in Rotated Sorted Array

#include <stdio.h>
#include <vector>

class Solution {
public:
    int search(std::vector<int>& nums, int target) {
        int begin = 0;
        int end = nums.size() - 1;
        while(begin <= end){
            int mid = (begin + end) / 2;
            if (target == nums[mid]){ //1、刚好在中间 
                return mid;
            }
            else if (target < nums[mid]){ //2、小于中间元素 
                if (nums[begin] < nums[mid]){ //如：[9,12,15,20,1,3,6,7] 
                    if (target >= nums[begin]){ //target在左边元素区间 
                        end = mid - 1;
                    }
                    else{ //target在右边元素区间 
                        begin = mid + 1;
                    }
                }
                else if (nums[begin] > nums[mid]){ //如：[20,1,3,6,7,9,12,15] 
                    end = mid -1;
                }
                else if (nums[begin] == nums[mid]){ //如：[3,1] 
                    begin = mid + 1;
                }
            }
            else if (target > nums[mid]){ //3、同理 
                if (nums[begin] < nums[mid]){
                    begin = mid + 1;
                }
                else if (nums[begin] > nums[mid]){
                    if (target >= nums[begin]){
                        end = mid - 1;
                    }
                    else{
                        begin = mid + 1;
                    }
                }
                else if (nums[begin] == nums[mid]){
                    begin = mid + 1;
                }
            }
        }
        return -1;
    }
};

int main(){
    int test[] = {9, 12, 15, 20, 1, 3, 6, 7}; //旋转后的数组 
    std::vector<int> nums;
    Solution solve;
    for (int i = 0; i < 8; i++){
        nums.push_back(test[i]);
    }
    for (int i = 0; i < 22; i++){
        printf("%d : %d\n", i, solve.search(nums, i));
    }
    return 0;
}

预备知识：二叉查找树基础知识

1）二叉查找树（Binary Search Tree），具有下列性质：
1、若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
2、若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
3、左、右子树也分别为二叉排序树。
4、等于的情况只能出现在左子树或右子树中的某一侧。

2）二叉查找树插入节点

• 二叉查找树的插入

#include <stdio.h>
#include <vector>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void BST_insert(TreeNode *node, TreeNode *insert_node){
    if (insert_node->val < node->val){ //1、小于当前节点 
        if (node->left){ //左孩子非空 
            BST_insert(node->left, insert_node);
        }
        else{ //左孩子空，直接插入 
            node->left = insert_node;
        }
    }
    else{ //2、同理
        if (node->right){
            BST_insert(node->right, insert_node);
        }
        else{
            node->right = insert_node;
        }
    }
}

void preorder_print(TreeNode *node,int layer){ //前序遍历 
    if (!node){
        return;
    }
    printf("[%d]\n", node->val);
    preorder_print(node->left, layer + 1);
    preorder_print(node->right, layer + 1);
}

int main(){
    TreeNode root(8);
    std::vector<TreeNode *> node_vec;
    int test[] = {3, 10, 1, 6, 15};
    for (int i = 0; i < 5; i++){ //构建链表 
        node_vec.push_back(new TreeNode(test[i]));
    }
    for (int i = 0; i < node_vec.size(); i++){ //构建二叉查找树 
        BST_insert(&root, node_vec[i]);
    }
    preorder_print(&root, 0);
    return 0;
}

• 二叉查找树的查找

#include <stdio.h>
#include <vector>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool BST_search(TreeNode *node, int value){
    if (node->val == value){ //找到 
        return true;
    }
    if (value < node->val){ //小于该节点元素 
        if (node->left){ //左孩子非空，继续查找 
            return BST_search(node->left, value);
        }
        else{ //未找到 
            return false;
        }
    }
    else{ //大于该节点元素 
        if (node->right){ //右孩子非空，继续查找 
            return BST_search(node->right, value);
        }
        else{ //未找到 
            return false;
        }
    }
}

int main(){
    TreeNode a(8);
    TreeNode b(3);
    TreeNode c(10);
    TreeNode d(1);
    TreeNode e(6);
    TreeNode f(15);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.right = &f;
    for (int i = 0; i < 20; i++){ //查找元素 0~19
        if (BST_search(&a, i)){
            printf("%d （√）\n", i);
        }
        else{
            printf("%d （×）\n", i);
        }
    }
    return 0;
}

例4：二叉查找树编码与解码（★★）

给定一个二叉查找树，实现对该二叉查找树编码与解码功能。编码即将该二叉查找树转为字符串，解码即将字符串转为二叉查找树。不限制使用何种编码算法。

1、编码

2、解码

• LeetCode 449.Serialize and Deserialize BST

#include <stdio.h>
#include <string>
#include <vector>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void BST_insert(TreeNode *node, TreeNode *insert_node){
    if (insert_node->val < node->val){
        if (node->left){
            BST_insert(node->left, insert_node);
        }
        else{
            node->left = insert_node;
        }
    }
    else{
        if (node->right){
            BST_insert(node->right, insert_node);
        }
        else{
            node->right = insert_node;
        }
    }
}

void change_int_to_string(int val, std::string &str_val){
    std::string tmp;
    while(val){
        tmp += val % 10 + '0';
        val /= 10;
    }
    for (int i = tmp.length()-1; i>=0; i--){
        str_val += tmp[i];
    }
    str_val += '#';
}

void BST_preorder(TreeNode *node, std::string &data){ //前序遍历并转字符 
    if (!node){
        return;
    }
    std::string str_val;
    change_int_to_string(node->val, str_val); //整型转字符 
    data += str_val;
    BST_preorder(node->left, data);
    BST_preorder(node->right, data);
}

class Codec {
public:
    std::string serialize(TreeNode* root) {
        std::string data;
        BST_preorder(root, data);
        return data;
    }
    TreeNode *deserialize(std::string data) {
        if (data.length() == 0){
            return NULL;
        }
        std::vector<TreeNode *> node_vec;
        int val = 0;
        for (int i = 0; i < data.length(); i++){
            if (data[i] == '#'){
                node_vec.push_back(new TreeNode(val));
                val = 0;
            }
            else{
                val = val * 10 + data[i] - '0';
            }
        }
        for (int i = 1; i < node_vec.size(); i++){
            BST_insert(node_vec[0], node_vec[i]);
        }
        return node_vec[0];
    }
};

void preorder_print(TreeNode *node,int layer){ //前序遍历并输出 
    if (!node){
        return;
    }
    printf("[%d] ", node->val);
    preorder_print(node->left, layer + 1);
    preorder_print(node->right, layer + 1);
}

int main(){
    TreeNode a(8);
    TreeNode b(3);
    TreeNode c(10);
    TreeNode d(1);
    TreeNode e(6);
    TreeNode f(15); 
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.left = &f;    
    Codec solve;    
    std::string data = solve.serialize(&a); //编码 
    printf("编码后：%s\n", data.c_str());
    TreeNode *root = solve.deserialize(data); //解码 
    printf("解码后：");
    preorder_print(root, 0); //前序遍历 
    return 0;
}

例5：逆序数（★★★）（二叉查找树）

已知数组nums，求新数组count，count[i] 代表了 nums[i] 右侧比其小的元素个数。

• LeetCode 315.Count of Smaller Numbers After Self

#include <stdio.h>
#include <vector>


struct BSTNode {  
    int val;
    int count; //记录左子树节点个数，为了计算 count_small 
    BSTNode *left;
    BSTNode *right;
    BSTNode(int x) : val(x), left(NULL), right(NULL), count(0) {}
};

void BST_insert(BSTNode *node, BSTNode *insert_node, int &count_small){ 
    if (insert_node->val <= node->val){ //插入节点小于当前节点 
        node->count++; //当前结点的 count
        if (node->left){ 
            BST_insert(node->left, insert_node, count_small);
        }
        else{ 
            node->left = insert_node;
        }
    }
    else{ //插入结点大于当前节点 
        count_small += node->count + 1; //插入结点的 count_small 
        if (node->right){
            BST_insert(node->right, insert_node, count_small);
        }
        else{
            node->right = insert_node;
        }
    }
}

class Solution {
public:
    std::vector<int> countSmaller(std::vector<int>& nums) {
        std::vector<int> result;
        std::vector<BSTNode *> node_vec;
        std::vector<int> count; //存储比当前元素小的个数 
        for (int i = nums.size() - 1; i >= 0; i--){ //1、逆向创建链表 [1,-2,5,3,1,9,-7,5] 
            node_vec.push_back(new BSTNode(nums[i]));
        }
        count.push_back(0); //第一个节点count=0
        for (int i = 1; i < node_vec.size(); i++){ //构建 
            int count_small = 0; //临时变量 
            BST_insert(node_vec[0], node_vec[i], count_small); //得到插入结点的 count_small 
            count.push_back(count_small); //
        }
        for (int i = node_vec.size() - 1; i >= 0; i--){ //2、count逆向存入result 
            delete node_vec[i]; //顺便释放链表内存 
            result.push_back(count[i]);
        }
        return result;
    }
};

int main(){
    int test[] = {5, -7, 9, 1, 3, 5, -2, 1};
    std::vector<int> nums;
    for (int i = 0; i < 8; i++){
        nums.push_back(test[i]);
    }
    Solution solve;
    std::vector<int> result = solve.countSmaller(nums);
    for (int i = 0; i < result.size(); i++){
        printf("%d（%d）\n", test[i],result[i]);
    }
    printf("\n");
    return 0;
}