数据结构的实践应用

简单介绍常用数据结构的应用

第2章数据结构基础

2.1 数组

基础

数组是将相同类型的元素存储于连续内存空间的数据结构，其长度不可变如下图所示，构建此数组需要在初始化时给定长度，并对数组每个索引元素赋值，代码如下：

// 初始化一个长度为 5 的数组 array
int array[5];
int array[] = {2, 3, 1, 0, 2};
// 初始化可变数组
vector<int> array;
// 向尾部添加元素
array.push_back(2);
array.push_back(3);

二分查找的实现

使用二分查找应该注意是否有序以及无重复元素
理解区间定义，处理好边界问题；
写二分法，区间的定义一般为两种*，左闭右闭即[left, right]，或者左闭右开即[left, right)
左闭右闭即[left, right]
while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
    while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
        int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
        if (nums[middle] > target) {
            right = middle - 1; // target 在左区间，所以[left, middle - 1]
        } else if (nums[middle] < target) {
            left = middle + 1; // target 在右区间，所以[middle + 1, right]
        } else { // nums[middle] == target
            return middle; // 数组中找到目标值，直接返回下标
        }
    }
    // 未找到目标值
    return -1;
}

如果定义 target 是在一个在左闭右开的区间里，也就是[left, right) ，那么二分法的边界处理方式则截然不同:

while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的

if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
    while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
        int middle = left + ((right - left) >> 1);
        if (nums[middle] > target) {
            right = middle; // target 在左区间，在[left, middle)中
        } else if (nums[middle] < target) {
            left = middle + 1; // target 在右区间，在[middle + 1, right)中
        } else { // nums[middle] == target
            return middle; // 数组中找到目标值，直接返回下标
        }
    }
    // 未找到目标值
    return -1;
}

leetcode35 查找插入位置

难点在与循环之后插入位置处理，应该从target所在区间角度考虑理解返回值

版本1

int searchInsert(vector<int>& nums, int target) {
    int n = nums.size();
    int left = 0;
    int right = n - 1; // 定义target在左闭右闭的区间里，[left, right]
    while (left <= right) { // 当left==right，区间[left, right]依然有效
        int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
        if (nums[middle] > target) {
            right = middle - 1; // target 在左区间，所以[left, middle - 1]
        } else if (nums[middle] < target) {
            left = middle + 1; // target 在右区间，所以[middle + 1, right]
        } else { // nums[middle] == target
            return middle;
        }
    }
    // 分别处理如下四种情况
    // 目标值在数组所有元素之前  [0, -1]
    // 目标值等于数组中某一个元素  return middle;
    // 目标值插入数组中的位置 [left, right]，return  right + 1
    // 目标值在数组所有元素之后的情况 [left, right]， return right + 1
    return right + 1;
}

核心思想：

由于采取左闭右闭的区间方式，最后一次判断肯定为区间[left,right],且left=right=middle
若最后一次查找执行为**(注意这里的的位置指的是在数组中的个数，而非下标)**
if (nums[middle] > target) middle=right+1为插入位置因为target的排序在nums[middle]的左边
else if (nums[middle] < target) left|=middle+1=right+1（while条件为<=)为插入位置

故 return right+1;

版本2

int searchInsert(vector<int>& nums, int target) {
    int n = nums.size();
    int left = 0;
    int right = n; // 定义target在左闭右开的区间里，[left, right)  target
    while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间
        int middle = left + ((right - left) >> 1);
        if (nums[middle] > target) {
            right = middle; // target 在左区间，在[left, middle)中
        } else if (nums[middle] < target) {
            left = middle + 1; // target 在右区间，在 [middle+1, right)中
        } else { // nums[middle] == target
            return middle; // 数组中找到目标值的情况，直接返回下标
        }
    }
    // 分别处理如下四种情况
    // 目标值在数组所有元素之前 [0,0)
    // 目标值等于数组中某一个元素 return middle
    // 目标值插入数组中的位置 [left, right) ，return right 即可
    // 目标值在数组所有元素之后的情况 [left, right)，return right 即可
    return right;
}

二分法查找边界问题

34. 在排序数组中查找元素的第一个和最后一个位置

注意重复元素
寻找右边界

// 二分查找，寻找target的右边界（不包括target）
// 如果rightBorder为没有被赋值（即target在数组范围的左边，例如数组[3,3]，target为2），为了处理情况一
int getRightBorder(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
    int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
    while (left <= right) { // 当left==right，区间[left, right]依然有效
        int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
        if (nums[middle] > target) {
            right = middle - 1; // target 在左区间，所以[left, middle - 1]
        } else { // 当nums[middle] == target的时候，更新left，这样才能得到target的右边界
            left = middle + 1;
            rightBorder = left;
        }
    }
    return rightBorder;
}

寻找左边界

// 二分查找，寻找target的左边界leftBorder（不包括target）
// 如果leftBorder没有被赋值（即target在数组范围的右边，例如数组[3,3],target为4），为了处理情况一
int getLeftBorder(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
    int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
    while (left <= right) {
        int middle = left + ((right - left) / 2);
        if (nums[middle] >= target) { // 寻找左边界，就要在nums[middle] == target的时候更新right
            right = middle - 1;
            leftBorder = right;
        } else {
            left = middle + 1;
        }
    }
    return leftBorder;
}

版本2

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int lfBord=0,rtBord=nums.size();
        int lf=0,rt=nums.size();
        // 找左边界
        while(lf<rt){
            int mid=lf+((rt-lf)>>1);
            if(nums[mid]>=target) rt=mid;
            else{
                lf=mid+1;
            }
             cout<<"左边界 mid"<<mid<<" "<<nums[mid]<<endl;
        }
        lfBord=lf;
        cout<<"one: "<<lf<<" "<<rt<<endl;
        lf=0,rt=nums.size();
        // 找右边界
        while(lf<rt){
            int mid=lf+((rt-lf)>>1);
            if(nums[mid]>target) rt=mid;
            else{
                lf=mid+1;
            }
            cout<<"右边界 mid"<<mid<<" "<<nums[mid]<<endl;
        }
        rtBord=rt-1;
        cout<<"one: "<<lf<<" "<<rt<<endl;
        if(lfBord<=rtBord) return {lfBord,rtBord};
        return {-1,-1};
    }
};

版本3

注意函数复用的特点；

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int lfBord=0,rtBord=nums.size();
        int lf=0,rt=nums.size();
        function<int(int lf,int rt,int t)> f =[&](int lf,int rt,int t)->int{
                while(lf<rt){
                        int mid=lf+((rt-lf)>>1);
                        if(nums[mid]>=t) rt=mid;
                        else{
                                lf=mid+1;
                        }
                }
                return rt;
        };
        
       lfBord=f(lf,rt,target);
       if(lfBord==rt||nums[lfBord]!=target) return {-1,-1};
       rtBord=f(lf,rt,target+1)-1;
//        cout<<lfBord<<" "<<rtBord;
        return {lfBord,rtBord};
        
    }
};

268. 丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中

思路：：排序+二分求左边界

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        // 对 nums 数组进行排序
        sort(nums.begin(), nums.end());
        // 定义左右指针
        int lf = 0, rt = nums.size();
        // 二分查找缺失的数字
        while (lf < rt) {
            int mid = lf + ((rt - lf) >> 1);
            if (nums[mid] != mid) {
                rt = mid;
            } else {
                lf = mid + 1;
            }
        }
        // 如果缺失的数字是最后一个数字，则返回 nums 的长度
        if (lf == nums.size()) {
            return nums.size();
        }
        // 否则返回缺失的数字
        return lf;
    }
};

双指针

leetcode209 最小长度子数组

class Solution 
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

88. 合并两个有序数组

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

思路：逆向双指针（正向双指针需要额外空间）

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // 定义三个指针，分别指向 nums1 的最后一个元素、nums2 的最后一个元素和 nums1 的最后一个位置
        int numEnd1 = m - 1, numEnd2 = n - 1, end = m + n - 1;
        // 从后往前遍历 nums1 和 nums2，将较大的元素放到 nums1 的最后面
        while (numEnd1 >= 0 && numEnd2 >= 0) {
            if (nums1[numEnd1] > nums2[numEnd2]) {
                nums1[end--] = nums1[numEnd1--];
            } else {
                nums1[end--] = nums2[numEnd2--];
            }
        }
        // 将 nums2 中剩余的元素全部放到 nums1 的前面
        while (numEnd2 >= 0) {
            nums1[end--] = nums2[numEnd2--];
        }
    }
};

求中位数

1093. 大样本统计

我们对 0 到 255 之间的整数进行采样，并将结果存储在数组 count 中：count[k] 就是整数 k 在样本中出现的次数。

计算以下统计数据:

minimum ：样本中的最小元素。
maximum ：样品中的最大元素。
mean ：样本的平均值，计算为所有元素的总和除以元素总数。
median ：
如果样本的元素个数是奇数，那么一旦样本排序后，中位数 median 就是中间的元素。
如果样本中有偶数个元素，那么中位数median 就是样本排序后中间两个元素的平均值。
mode ：样本中出现次数最多的数字。保众数是唯一的。
以浮点数数组的形式返回样本的统计信息 [minimum, maximum, mean, median, mode] 。与真实答案误差在 10-5 内的答案都可以通过。

输入：count = [0,1,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
输出：[1.00000,3.00000,2.37500,2.50000,3.00000]
解释：用count表示的样本为[1,2,2,2,3,3,3,3]。
最小值和最大值分别为1和3。
均值是(1+2+2+2+3+3+3+3) / 8 = 19 / 8 = 2.375。
因为样本的大小是偶数，所以中位数是中间两个元素2和3的平均值，也就是2.5。
众数为3，因为它在样本中出现的次数最多。

class Solution {
public:
    vector<double> sampleStats(vector<int>& count) {
        // 定义变量
        int n = count.size();
        int total = accumulate(count.begin(), count.end(), 0);
        double mean = 0.0;
        double median = 0.0;
        int minnum = 256;
        int maxnum = 0;
        int mode = 0;
        int left = (total + 1) / 2;
        int right = (total + 2) / 2;
        int cnt = 0;
        int maxfreq = 0;
        long long sum = 0;
        // 遍历 count 数组，计算平均数、中位数、最小值、最大值和众数
        for (int i = 0; i < n; i++) {
            sum += (long long)count[i] * i; // 计算总和
            if (count[i] > maxfreq) { // 更新众数
                maxfreq = count[i];
                mode = i;
            }
            if (count[i] > 0) { // 更新最小值和最大值
                if (minnum == 256) {
                    minnum = i;
                }
                maxnum = i;
            }
            if (cnt < right && cnt + count[i] >= right) { // 计算右中位数
                median += i;
            }
            if (cnt < left && cnt + count[i] >= left) { // 计算左中位数
                median += i;
            }
            cnt += count[i]; // 更新累加器
        }
        // 计算平均数和中位数
        mean = (double) sum / total;
        median = median / 2.0;
        // 返回结果
        return {(double)minnum, (double)maxnum, mean, median, (double)mode};
    }
};

2.2 链表

理论基础

链表以节点为单位，每个元素都是一个独立对象，在内存空间的存储是非连续的。链表的节点对象具有两个成员变量

struct ListNode {
    int val;        // 节点值
    ListNode *next; // 后继节点引用
    ListNode(int x) : val(x), next(NULL) {}
};
ListNode* creatList(vector<int>& v){
    ListNode* pHead= new ListNode(-1),*r;
    r=pHead;
    for(auto data:v){
        ListNode* s=new ListNode(data);
        r->next=s;
        r=s;
    }
    return pHead->next;
}

移除链表元素

设置虚拟头节点处理，统一操作

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
        ListNode* cur = dummyHead;
        while (cur->next != NULL) {
            if(cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

翻转链表

两种思路：从头翻转或者从尾部开始翻转

#方案1 双指针
ListNode* pre=NULL,*cur=pHead;
while(cur){
    ListNode* temp=cur->next;
    cur->next=pre;
    pre=cur;
    cur=temp;
}
return pre;
递归实现
class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }

};

#方案2 从尾部开始翻转
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr) return nullptr;
        if(head->next==nullptr) return head;
        ListNode phead=reverseList(head->next);
        head->next->next=head;
        head->next=nullptr;
        return phead;

    }
};

25. K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

class Solution {
public:
    pair<ListNode*,ListNode*> reverse(ListNode* head,ListNode* tail){
        ListNode* pre=nullptr;
        ListNode* cur=head;
        while(cur!=tail){
            ListNode* temp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=temp;
        }
        cur->next=pre;
        pre=cur;
        return{pre,head};
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* hair=new ListNode(0);
        hair->next=head;
        ListNode* pre=hair;

        while(head){
            ListNode* tail=pre;
            for(int i=0;i<k;++i){
               tail=tail->next;
               if(tail==nullptr){
                   return hair->next;
               }
            }
            ListNode* nex=tail->next;
            pair<ListNode*, ListNode*> result = reverse(head, tail);
            head = result.first;
            tail = result.second;

            pre->next=head;
            tail->next=nex;
            pre=tail;
            head=tail->next;

        }
        return hair->next;
    }
};

leetcode24 两两交换链表中节点

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
        ListNode* cur = dummyHead;
        while(cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* tmp = cur->next; // 记录临时节点
            ListNode* tmp1 = cur->next->next->next; // 记录临时节点

            cur->next = cur->next->next;    // 步骤一
            cur->next->next = tmp;          // 步骤二
            cur->next->next->next = tmp1;   // 步骤三

            cur = cur->next->next; // cur移动两位，准备下一轮交换
        }
        return dummyHead->next;
    }
};

链表相交节点问题链表相交

两链表相加遍历思想，理解相加的思想为什么不会出现死循环

链表环入口问题环形链表

初始采用不同倍率速度（2倍）

相遇时b点有：step2=2*step1 2*(x+ab)=x+ab+n(ab+bca);

公式两边消除化简

x=(n-1)*(ab+bca)+bca 可以推导出第二次相遇在入口处

2.3 哈希表

理论基础

哈希表是根据关键码的值而直接进行访问的数据结构

一般哈希表都是用来快速判断一个元素是否出现集合里

例如要查询一个名字是否在这所学校里。
要枚举的话时间复杂度是$O(n)$，但如果使用哈希表的话，只需要$O(1)$就可以做到。
我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。
将学生姓名映射到哈希表上就涉及到了hash function ，也就是哈希函数

哈希函数

哈希函数

一般哈希碰撞有两种解决方法，拉链法和线性探测法

常见的三种哈希结构

数组
set （集合）
map(映射)

集合	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::set	红黑树	有序	否	否	$O(\log n)$	$O(\log n)$
std::multiset	红黑树	有序	是	否	$O(\log n)$	$O(\log n)$
std::unordered_set	哈希表	无序	否	否	$O(1)$	$O(1)$

std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加

映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::map	红黑树	key有序	key不可重复	key不可修改	$O(\log n)$	$O(\log n)$
std::multimap	红黑树	key有序	key可重复	key不可修改	$O(\log n)$	$O(\log n)$
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	$O(1)$	$O(1)$

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）

当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset

那么再来看一下map ，在map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。

虽然·std::set、std::multise 的底层实现是红黑树，不是哈希表，但是std::set、std::multiset 依然使用哈希函数来做映射，只不过底层的符号表使用了红黑树来存储数据，所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map也是一样的道理

这里在说一下，一些C++的经典书籍上例如STL源码剖析，说到了hash_set hash_map，这个与unordered_set，unordered_map又有什么关系呢？

实际上功能都是一样一样的，但是unordered_set在C++11的时候被引入标准库了，而hash_set并没有，所以建议还是使用unordered_set比较好，这就好比一个是官方认证的，hash_set，hash_map 是C++11标准之前民间高手自发造的轮子

总结：当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法

但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找

常见案例

leetcode242 有效的字母异位词

map的简单使用

/*
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = "anagram", t = "nagaram" 输出: true
示例 2: 输入: s = "rat", t = "car" 输出: false
说明: 你可以假设字符串只包含小写字母
*/
bool isAnagram(string s, string t) {
    unordered_map<char,int> map;
    for(auto c:s) ++map[c];
    //for(auto c:map) cout<<c.first<<" "<<c.second<<endl;
    for(auto c:t){
        if(map[c]>0) --map[c];
        else return false;
    }
    for(auto it:map){
        if(it.second!=0) return false;
    }
    return true;
}

也可以用数组实现，直接使用set，map不仅占用空间比数组大，
而且速度要比数组慢，把数值映射到key上都要做hash计算的

leetcode349 两个数组的交集

unordeered_set以及set迭代器的使用

/*
给定两个数组 nums1 和 nums2 ，返回 它们的交集 
输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
*/
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for (int num : nums2) {
            // 发现nums2的元素 在nums_set里又出现过
            if (nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

leetcode1 两个数组之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路
本题呢，则要使用map，那么来看一下使用数组和set来做哈希法的局限。
数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，
因为要返回x 和 y的下标。所以set 也不能用。
此时就要选择另一种数据结构：map ，map是一种key value的存储结构，
可以用key保存数值，用value在保存数值所在的下标。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map_num ;
        vector<int> v;
        for(int i=0;i<nums.size();++i){
            if(map_num.find(target-nums[i])!=map_num.end()){
                v.push_back(map_num[target-nums[i]]);
                v.push_back(i);
            }
            map_num.emplace(nums[i],i);
        }
        
        return v;
    }
};

leetcode383 赎金信

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
注意：
你可以假设两个字符串均只含有小写字母。
canConstruct(“a”, “b”) -> false
canConstruct(“aa”, “ab”) -> false
canConstruct(“aa”, “aab”) -> true

思路

在本题的情况下，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。所以数组更加简单直接有效

其他题目

leetcode15 三数之和 双指针

思路：先排序去重双指针

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(),nums.end());
        int left=0,right=nums.size()-1;
        for(int i=0;i<nums.size();++i){
            // 最小值>0 没有结果
            if(nums[i]>0) return ans;

            // 去重
            if(i>0&&nums[i]==nums[i-1]) continue;
            left=i+1;
            right=nums.size()-1;
            while(left<right){
                int val=nums[i]+nums[left]+nums[right];
                // 右边偏大，向左移动选取更小的
                if(val>0){
                    --right;
                    while(left<right&&nums[right]==nums[right+1]) --right;
                }
                else if(val<0){// 左边偏小，向右边移动选取更大的
                    ++left;
                    while(left<right&&nums[left]==nums[left-1]) ++left;
                }
                else{
                    ans.push_back({nums[i],nums[left],nums[right]});
                    --right;
                    ++left;
                    while(left<right&&nums[right]==nums[right+1]) --right;
                    while(left<right&&nums[left]==nums[left-1]) ++left;
                }
            }
        }
        return ans;

    }
};

leetcode18 四数之和 双指针

2.4 字符串

理论基础

双指针法翻转字符串
leetcode344 反转字符串
局部反转+整体反转
剑指Offer58-II.左旋转字符

KMP算法实现strStr()
leetcode28 实现strStr()

实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1: 输入: haystack = “hello”, needle = “ll” 输出: 2
示例 2: 输入: haystack = “aaaaa”, needle = “bba” 输出: -1

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(), s.begin() + n);
        reverse(s.begin() + n, s.end());
        reverse(s.begin(), s.end());
        return s;
    }
};

字符串与数值的转化

熟悉to_string(),stoi(),stod()

string s="3.1415";
int a= 12345;
doulble d= stod(s);
string str=to_string(a);

字符串与数值的转化

参考 c++primer 9.5.5

KMP算法

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了
1. 前缀表

作用:前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。
记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀

前缀:是指不包含最后一个字符的所有以第一个字符开头的连续子串；
后缀:是指不包含第一个字符的所有以最后一个字符结尾的连续子串
最长相等前后缀

2. 前缀表与next数组

next数组就可以是前缀表，常用的两种实现:
1.把前缀表统一减一
2.右移一位，初始位置为-1之后作为next数组

构造next[]

构造next数组其实就是计算模式串s，前缀表的过程。主要有如下三步(以前缀表统一减一为例)：

初始化
处理前后缀不相同的情况
处理前后缀相同的情况

初始化

定义两个指针i和j，j指向前缀起始位置，i指向后缀起始位置
然后还要对next数组进行初始化赋值，如下：
1
2
int j = -1;
next[0] = j;
j 为什么要初始化为 -1呢，因为之前说过前缀表要统一减一的操作仅仅是其中的一种实现，
我们这里选择j初始化为-1，下文我还会给出j不初始化为-1的实现代码。
next[i] 表示 i（包括i）之前最长相等的前后缀长度（其实就是 j）
所以初始化next[0] = j 。
处理前后缀不相同的情况
因为j初始化为-1，那么i就从1开始，进行s[i] 与 s[j+1]的比较。
所以遍历模式串s的循环下标i 要从 1开始，代码如下：
for (int i = 1; i < s.size(); i++) {
如果 s[i] 与 s[j+1]不相同，也就是遇到前后缀末尾不相同的情况，就要向前回退
next[j]就是记录着j（包括j）之前的子串的相同前后缀的长度
那么 s[i] 与 s[j+1] 不相同，就要找 j+1前一个元素在next数组里的值（就是next[j]）
1
2
3
while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
j = next[j]; // 向前回退
}
处理前后缀相同的情况
如果 s[i] 与 s[j + 1] 相同，那么就同时向后移动i 和j 说明找到了相同的前后缀，
同时还要将j（前缀的长度）赋给next[i], 因为next[i]要记录相同前后缀的长度
1
2
3
4
if (s[i] == s[j + 1]) { // 找到相同的前后缀
j++;
}
next[i] = j;

整体代码如下

void getNext(int* next, const string& s){
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // 注意i从1开始
        while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
            j = next[j]; // 向前回退
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后缀
            j++;
        }
        next[i] = j; // 将j（前缀的长度）赋给next[i]
    }
}

next[]构造过程
构造next[]数组

3. 利用next数组来做匹配

int j = -1; // 因为next数组里记录的起始位置为-1
for (int i = 0; i < s.size(); i++) { // 注意i就从0开始
    while(j >= 0 && s[i] != t[j + 1]) { // 不匹配
        j = next[j]; // j 寻找之前匹配的位置
    }
    if (s[i] == t[j + 1]) { // 匹配，j和i同时向后移动
        j++; // i的增加在for循环里
    }
    if (j == (t.size() - 1) ) { // 文本串s里出现了模式串t
        return (i - t.size() + 1);
    }
}

前缀表统一减一 C++代码实现

class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = -1;
        next[0] = j;
        for(int i = 1; i < s.size(); i++) { // 注意i从1开始
            while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
                j = next[j]; // 向前回退
            }
            if (s[i] == s[j + 1]) { // 找到相同的前后缀
                j++;
            }
            next[i] = j; // 将j（前缀的长度）赋给next[i]
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = -1; // // 因为next数组里记录的起始位置为-1
        for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始
            while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
                j = next[j]; // j 寻找之前匹配的位置
            }
            if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
                j++; // i的增加在for循环里
            }
            if (j == (needle.size() - 1) ) { // 文本串s里出现了模式串t
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

前缀表（不减一不右移）C++实现

class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = 0;
        for (int i = 0; i < haystack.size(); i++) {
            while(j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == needle.size() ) {
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

leetcode459 重复的子字符串

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: “abab”
输出: True
解释: 可由子字符串 “ab” 重复两次构成。
思路
next[]为相等前后缀表统一减一;
next[len-1]!=-1 最长串存在相等前后缀
abcabcabc
len_s-(next[len_s-1]+1)为一个周期
若len为周期倍数，返回true

class Solution {
public:
    void getNext (int* next, const string& s){
        next[0] = -1;
        int j = -1;
        for(int i = 1;i < s.size(); i++){
            while(j >= 0 && s[i] != s[j+1]) {
                j = next[j];
            }
            if(s[i] == s[j+1]) {
                j++;
            }
            next[i] = j;
        }
    }
    bool repeatedSubstringPattern (string s) {
        if (s.size() == 0) {
            return false;
        }
        int next[s.size()];
        getNext(next, s);
        int len = s.size();
        if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0) {
            return true;
        }
        return false;
    }
};

2.5 栈与队列

容器以及容器适配器

熟悉 vector,deque的简单使用
顺序容器类型

顺序容器的相关操作

向容器中添加元素
删除容器中元素
访问容器中元素

迭代器

1
2
3

//获取容器的迭代器
c.begin()
c.end()

容器适配器：

stack
queue
priority_queue

容器适配器的类型以及操作

vector

优点：
A、支持随机访问，访问效率高和方便，它像数组一样被访问，即支持[ ] 操作符和vector.at()。
B、节省空间，因为它是连续存储，在存储数据的区域都是没有被浪费的，但是要明确一点vector 大多情况下并不是满存的，在未存储的区域实际是浪费的。
缺点：
A、在内部进行插入、删除操作效率非常低。
B、只能在vector 的最后进行push 和pop ，不能在vector 的头进行push 和pop 。
C、 当动态添加的数据超过vector 默认分配的大小时要进行内存的重新分配、拷贝与释放，这个操作非常消耗能。
定义：vector<数据类型>名称
v.push_back():压入到最后一个
v.pop_back()：弹出最后一个
v.size():向量长度

stack

定义：stack<数据类型>名称
s.pop(): 栈顶元素出栈
s.push(value): 元素入栈
s.top(): 返回栈顶元素，元素不弹出

deque

deque双端队列
随机访问每个元素，所需要的时间为常量
弹出队首元素：q.pop_back()无返回值
弹出队尾元素：q.pop_front()无返回值
压入队尾：q.push_back(x)
压入队首：q.push_front(x)
取队首：q.front()
取队尾：q.back()

queue队列

定义：queue<数据类型> 队列名称
queue入队，如例：q.push(x)；将x 接到队列的末端。
queue出队，如例：q.pop()；弹出队列的第一个元素，注意，并不会返回被弹出元素的值。
访问queue队首元素，如例：q.front()，即最早被压入队列的元素。
访问queue队尾元素，如例：q.back()，即最后被压入队列的元素。
判断queue队列空，如例：q.empty()，当队列空时，返回true。
访问队列中的元素个数，如例：q.size()。

priority_queue优先队列

C/C++排序函数中cmp()比较函数的写法

标准C库：
函数原型void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void * ))

int cmp(const void *a ,const void *b)
{
	return *(int *)a - *(int *)b ;			//从小到大排序，不能写成 return a < b 这种形式
}

C++函数sort（）
sort（）函数定义在c++标准头文件的里面
函数原型void sort( iterator start, iterator end, StrictWeakOrdering cmp )

bool cmp(int a ,int b)
{
	return a < b ;		//从小到大排序，注意与c的区别
}

在C++中，我们经常需要用到set，map等容器，他们的cmp基本写法都与sort的相同，当然set，map的cmp是函数对象;

以set为例，set关联容器对关键字类型有一些限制，关键字类型必须定义比较操作，
默认情况下，标准库使用关键字类型的<运算符来比较两个关键字。
当关键字类型是用户自定义类型时，为了容器中关键字类型正确，我们有三种方式提供正确的关键字类型。

在关键字类型中对<运算符进行重载

#include<iostream>
#include<set>
using namespace std;
 
class Node
{
public:
	int start;
	int end;
	Node(){}
	Node(int s, int e) :start(s), end(e)
	{
	
	}
	bool operator<(const Node &other) const
	{
		return start < other.start;
	}
};
int main(void)
{
	multiset<Node> m;
	m.insert(Node(4, 5));
	m.insert(Node(3, 4));
	m.insert(Node(6, 7));
	system("pause");
	return 0;
}

使用重载函数调用运算符类型的对象进行比较操作,定义方式：multiset<Node,CompareClassNode> m;

#include<iostream>
#include<set>
using namespace std;
 
class Node
{
public:
	int start;
	int end;
	Node(){}
	Node(int s, int e) :start(s), end(e)
	{
	
	}
};
 
class CompareClassNode
{
public:
	bool operator()(const Node &lhs, const Node &rhs)
	{
		return lhs.start < rhs.start;
	}
};
 
int main(void)
{
	multiset<Node,CompareClassNode> m;
	m.insert(Node(4, 5));
	m.insert(Node(3, 4));
	m.insert(Node(6, 7));
	system("pause");
	return 0;
}

使用自定义比较函数。必须这样定义multiset<Node, decltype(compareNode)*> m(compareNode)

==区分自定义比较函数与重写仿函数== multiset<Node,CompareClassNode> m;

decltype是C++11新增的一个关键字，和auto的功能一样，用来在编译时期进行自动类型推导,选择并返回操作数的数据类型，在此过程中，编译器分析表达式并得到它的类型，却不实际计算表达式的值。

auto varName=value;
decltype(exp) varName=value;

auto根据=右边的初始值推导出变量的类型，decltype根据exp表达式推导出变量的类型，跟=右边的value没有关系
auto要求变量必须初始化，这是因为auto根据变量的初始值来推导变量类型的，如果不初始化，变量的类型也就无法推导
而decltype不要求，因此可以写成decltype(exp) varName;

int getSize();

int main(void)
{
    int tempA = 2;
    
    /*1.dclTempA为int.*/
    decltype(tempA) dclTempA;
    /*2.dclTempB为int，对于getSize根本没有定义，但是程序依旧正常，因为decltype只做分析，并不调用getSize().*/
    decltype(getSize()) dclTempB;

    return 0;
}

自定义比较函数案例

#include<iostream>
#include<set>

using namespace std;

class Node
{
public:
  int start;
  int end;
  Node(){}
  Node(int s, int e) :start(s), end(e)
  {
  
  }
};

bool compareNode(const Node &lhs,const Node &rhs)
{
  return lhs.start < rhs.start;
}


int main(void)
{
  multiset<Node, decltype(compareNode)*> m(compareNode);
  m.insert(Node(4, 5));
  m.insert(Node(3, 4));
  m.insert(Node(6, 7));
  system("pause");
  return 0;
}

操作基本和队列相同

top 访问队头元素
empty 队列是否为空
size 返回队列内元素个数
push 插入元素到队尾 (并排序)
emplace 原地构造一个元素并插入队列
pop 弹出队头元素
swap 交换内容

定义:

priority_queue<Type, Container, Functional>

1
2
3

template <typename T, typename Container = std::vector<T>,
          typename Compare = std::less<typename Container::value_type>>
class priority_queue;

priority_queue 的第三个参数是一个可选项，它定义了一个比较函数对象，用于指定优先队列中元素的排序方式。这个比较函数对象必须实现一个 () 操作符，接收两个元素作为参数，返回一个布尔值表示它们的相对顺序。当然，如果不传入比较函数对象，那么默认情况下 priority_queue 将使用 std::less 进行排序，即将最大元素放在队首。

当我们自定义数据类型时，通常需要实现自定义的比较函数。在 priority_queue 中，可以通过函数指针或者函数对象来传入比较函数。

使用函数指针时，需要提供一个指向函数的指针，该函数必须具有与比较对象相同的参数类型和返回类型。在创建 priority_queue 对象时，可以通过使用 decltype 来自动推导函数指针类型，如下所示：

bool cmp(int a, int b) {
    return a > b;
}

priority_queue<int, vector<int>, decltype(&cmp)> q(&cmp);

这里，第三个参数使用了函数指针 decltype(&cmp)，它会根据函数指针类型自动推导比较函数对象类型。

另一种方法是使用函数对象，即定义一个具有 () 操作符的类，如下所示：

struct cmp {
    bool operator() (int a, int b) {
        return a > b;
    }
};

priority_queue<int, vector<int>, cmp> q;

这里，我们定义了一个名为 cmp 的结构体，并重载了 () 操作符，然后将 cmp 作为比较函数对象传递给 priority_queue。当创建 priority_queue 对象时，我们只需要使用 cmp 类型作为第三个参数即可。

总之，使用函数对象可以实现更为复杂的比较逻辑，但需要写更多的代码；使用函数指针则比较简单，但比较逻辑必须封装在一个函数中。

Type 就是数据类型，
Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），
Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆

//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;

// greater和less是std实现的两个仿函数
// 就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，
// 这个类就有了类似函数的行为，就是一个仿函数类了

实例

基本类型例子

#include<iostream>
#include <queue>
using namespace std;
int main() 
{
    //对于基础类型 默认是大顶堆
    priority_queue<int> a; 
    //等同于 priority_queue<int, vector<int>, less<int> > a;
    
    priority_queue<int, vector<int>, greater<int> > c;  //这样就是小顶堆
    priority_queue<string> b;

    for (int i = 0; i < 5; i++) 
    {
        a.push(i);
        c.push(i);
    }
    while (!a.empty()) 
    {
        cout << a.top() << ' ';
        a.pop();
    } 
    cout << endl;

    while (!c.empty()) 
    {
        cout << c.top() << ' ';
        c.pop();
    }
    cout << endl;

    b.push("abc");
    b.push("abcd");
    b.push("cbd");
    while (!b.empty()) 
    {
        cout << b.top() << ' ';
        b.pop();
    } 
    cout << endl;
    return 0;
}

pari的比较，先比较第一个元素，第一个相等比较第二个(默认构建大顶堆)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() 
{
    priority_queue<pair<int, int> > a;
    pair<int, int> b(1, 2);
    pair<int, int> c(1, 3);
    pair<int, int> d(2, 5);
    a.push(d);
    a.push(c);
    a.push(b);
    while (!a.empty()) 
    {
        cout << a.top().first << ' ' << a.top().second << '\n';
        a.pop();
    }
}
/* 输出
2 5
1 3
1 2
*/

对于自定义类型

运算符重载

重写仿函数

#include <iostream>
#include <queue>
using namespace std;

//方法1
struct tmp1 //运算符重载<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大顶堆
    }
};

//方法2
struct tmp2 //重写仿函数
{  
    // 默认是less函数 
    // 返回true时，a的优先级低于b的优先级（a排在b的后面）

    bool operator() (tmp1 a, tmp1 b) 
    {
        return a.x < b.x; //大顶堆
    }
};


//方法3 小顶堆
struct tmp3 //重写仿函数
{  
    // 默认是less函数
    // 返回true时，a的优先级低于b的优先级（a排在b的后面）
    bool operator() (tmp1 a, tmp1 b) 
    {
        return a.x > b.x; //小顶堆
    }
};

int main() 
{
    tmp1 a(1);
    tmp1 b(2);
    tmp1 c(3);
    priority_queue<tmp1> d;
    d.push(b);
    d.push(c);
    d.push(a);
    while (!d.empty()) 
    {
        cout << d.top().x << '\n';
        d.pop();
    }
    cout << endl;

    priority_queue<tmp1, vector<tmp1>, tmp2> f;
    f.push(c);
    f.push(b);
    f.push(a);
    while (!f.empty()) 
    {
        cout << f.top().x << '\n';
        f.pop();
    }


}

堆的实现

尝试用泛型编程实现堆

#include<iostream>
#include<vector>

using namespace std;
class Heap {
private:
    int N = 0;
    vector<int> heap;// 这个没有意义的是
public:

    Heap() {
        N = 0;
    }
    // 获取最大值
    int top() {
        return heap[0];
    }

    // 数据首先插入末尾 ,然后上浮
    void push(int k) {
        heap.push_back(k); // 直接放到后面, 然后上浮
        this->N++;
        swim(heap.size() - 1);
        // print();
    }

    // 删除最大值, 最后一位放到开头, 然后在下沉
    void pop() {
        heap[0] = heap.back(); // 最后一位上位, 然后在下沉
        heap.pop_back();
        this->N--;
        sink(0);
        // print();
    }

    // 下面是小根堆
    // 上浮, 在每次插入数据的时候
    void swim(int pos) {
        while (pos > 0 && heap[(pos - 1) / 2] < heap[pos]) {  // 子节点大于父节点 
            swap(heap[(pos - 1) / 2], heap[pos]); // 交换两个位置
            pos = (pos - 1) / 2; // 节点切换到上一层 
        }
    }

    // 下沉, 在每次删除数据的时候
    void sink(int pos) {
        int i;
        while (2 * pos + 2 < N) { //2pos是子节点
            i = 2 * pos + 1;
            if (i < N && heap[i] < heap[i + 1]) i++; // i指向子节点中最大的
            if (heap[pos] >= heap[i]) break; // 已经找到pos应该的位置了
            swap(heap[pos], heap[i]);
            pos = i;
        }
    }

    void print() {
        cout << "打印heap所有值" << endl;
        for (const auto& num : heap) {
            cout << num << " ";
        }cout << endl;
    }
};

void test() {
    Heap * heap=new Heap();
    int a[] = { 1,2,3,4 };
    int b = 3;
    heap->push(a[0]); heap->print();
    heap->push(a[1]); heap->print();
    heap->push(a[2]); heap->print();
    heap->push(a[3]); heap->print();


    heap->pop(); heap->print();
    heap->pop(); heap->print();
    heap->pop(); heap->print();
    cout << heap->top() << endl;
}

int main() {
    test();


    return 0;
}

手撕堆排序

#include <iostream>
#include <algorithm>
using namespace std;
void max_heapify(int arr[], int start, int end) {
    //建立父节点指标和子节点指标
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { //若子节点指标在范围内才做比较
        if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的
            son++;
        if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完毕，直接跳出函数
            return;
        else { //否则交换父子内容再继续子节点和孙节点比较
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}
void heap_sort(int arr[], int len) {
    //初始化，i从最后一个父节点开始调整
    for (int i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    //先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}
int main() {
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    for (int i = 0; i < len; i++)
        cout << arr[i] << ' ';
    cout << endl;
    return 0;
}

利用deque构造单调队列

leetcode239 滑动窗口最大值

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队里里的元素数值是由大到小的

注意理解：push()的实现保证了pop() 当前最早元素nums[i-k]时如果该元素在队里，必然是front()位置

维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列

class MyQueue { //单调队列（从大到小）
public:
    deque<int> que; // 使用deque来实现单调队列
    // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
    // 同时pop之前判断队列当前是否为空。
    void pop(int value) {
        if (!que.empty() && value == que.front()) {
            que.pop_front();
        }
    }
    // 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
    // 这样就保持了队列里的数值是单调从大到小的了。
    void push(int value) {
        while (!que.empty() && value > que.back()) {
            que.pop_back();
        }
        que.push_back(value);

    }
    // 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
    int front() {
        return que.front();
    }
};

构造堆或者利用priority_queue
leetcode347 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

构造小顶堆，当堆满后每次pop()为当前最小频率，故而n-k次pop()后，

n-k个相对要小的频率pop()出剩下前K大的频率

// 时间复杂度：O(nlogk)
// 空间复杂度：O(n)
class Solution {
public:
    // 小顶堆
    class comparision{
    public:
        bool operator()(const pair<int,int>& a,const pair<int,int>& b){// 默认重载< 操作符，数据大反而优先级小
            return a.second>b.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> map_nums;
        // 统计频率
        for(int c:nums){
            map_nums[c]++;
        }

        priority_queue<pair<int,int>,vector<pair<int,int>>,comparision> que;
        for(auto iter=map_nums.begin();iter!=map_nums.end();++iter){
            que.push(*iter);
            if(que.size()>k){
                que.pop();
            }
        }
        vector<int> result;
        while(que.size()>0){
            result.push_back(que.top().first);
            que.pop();
        }
        return result;
    }
};

// 时间复杂度：O(nlogk)
// 空间复杂度：O(n)
class Solution {
public:
    // 小顶堆
    class mycomparison {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 要统计元素出现频率
        unordered_map<int, int> map; // map<nums[i],对应出现的次数>
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }

        // 对频率排序
        // 定义一个小顶堆，大小为k
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

        // 用固定大小为k的小顶堆，扫面所有频率的数值
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
                pri_que.pop();
            }
        }

        // 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;

    }
};

单调栈

1019. 链表中的下一个更大节点

给定一个长度为 n 的链表 head

对于列表中的每个节点，查找下一个更大节点的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值严格大于它的值。

返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。

输入：head = [2,1,5]
输出：[5,5,0]
输入：head = [2,7,4,3,5]
输出：[7,0,5,5,0]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<int> ans;
    stack<int> myStack;
    void getNext(ListNode* head,int i){
        if(head==nullptr){
            ans=vector<int>(i);
            return;
        }
        getNext(head->next,i+1);
        while(!myStack.empty()&&head->val>=myStack.top()) myStack.pop();
        if(!myStack.empty()) ans[i]=myStack.top(); 
        else ans[i]=0;
        myStack.push(head->val);
    }
    vector<int> nextLargerNodes(ListNode* head) {
        getNext(head,0);
        return ans;
    }
};

2.6 树

树的生成

定义

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

构建二叉树:生成TreeNode数组思想

// 根据数组构造二叉树
TreeNode* construct_binary_tree(const vector<int>& vec) {
    vector<TreeNode*> vecTree (vec.size(), NULL);
    TreeNode* root = NULL;
    // 把输入数值数组，先转化为二叉树节点数组
    for (int i = 0; i < vec.size(); i++) {
        TreeNode* node = NULL;
        if (vec[i] != -1) node = new TreeNode(vec[i]); // 用 -1 表示null
        vecTree[i] = node;
        if (i == 0) root = node;
    }
    // 遍历一遍，根据规则左右孩子赋值就可以了
    // 注意这里 结束规则是 i * 2 + 2 < vec.size()，避免空指针
    for (int i = 0; i * 2 + 2 < vec.size(); i++) {
        if (vecTree[i] != NULL) {
            // 线性存储转连式存储关键逻辑
            vecTree[i]->left = vecTree[i * 2 + 1];
            vecTree[i]->right = vecTree[i * 2 + 2];
        }
    }
    
    return root;
}

二叉树的性质

以根节点为第一层开始计算

非空二叉树第 i 层最多 2^(i-1) 个结点（i >= 1）
深度为 k 的二叉树最多 2^k - 1 个结点（k >= 1）
度为 0 的结点数为 n₀，度为 2 的结点数为 n₂，则 n₀ = n₂ + 1
设B为分支总数，则n = B+1.由于这些分支是由度为1或2的结点射出的，所以又有B = n₀+ n₂*2
有 n 个结点的完全二叉树深度 k = ⌊ log₂(n) ⌋ + 1
对于含 n 个结点的完全二叉树中编号为 i （1 <= i <= n）的结点
1. 若 i = 1，为根，否则双亲为 ⌊ i / 2 ⌋
2. 若 2i > n，则 i 结点没有左孩子，否则孩子编号为 2i
3. 若 2i + 1 > n，则 i 结点没有右孩子，否则孩子编号为 2i + 1
4. 第k层最后一个节点编号 2^(k)-1
5. 第k层第一个节点编号 2^(k-1)
6. 第k层第m个节点编号 2^(k-1)+m-1
7. 左子节点编号= 2*父节点编号
8. 对于根节点从0开始编号则：4-5-6规则减一左子节点编号= 2*父节点编号+1

编号的推导问题

由父节点推导孩子节点编号
由孩子节点编号推导父节点
- 对于根节点从0开始编号 m
  父节点编号f=⌊(m-1)/2 ⌋
- 对于根节点从1开始编号 m
  父节点编号f=⌊ (m)/2 ⌋

二叉树的遍历

递归实现
- 确定确定递归函数的参数和返回值
- 确定终止条件
- 确定单层递归的逻辑

先序遍历

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

迭代遍历

前序遍历可以利用栈实现

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                       // 中
            st.pop();
            result.push_back(node->val);
            if (node->right) st.push(node->right);           // 右（空节点不入栈）
            if (node->left) st.push(node->left);             // 左（空节点不入栈）
        }
        return result;
    }
};

中序遍历（迭代法）

因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点

中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的

在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                st.pop();
                result.push_back(cur->val);     // 中
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

后序遍历
先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了
前序遍历的访问顺序与处理顺序一致的特点

 class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);
            if (node->left) st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）
            if (node->right) st.push(node->right); // 空节点不入栈
        }
        reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
        return result;
    }
};

二叉树的统一迭代

统一风格写法思想：

我们以中序遍历为例，仅仅使用栈的话，无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。
那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。
要处理的节点放入栈之后，紧接着放入一个空指针作为标记。这种方法也可以叫做标记法

中序遍历

 class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node->right) st.push(node->right);  // 添加右节点（空节点不入栈）

                st.push(node);                          // 添加中节点
                st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。

                if (node->left) st.push(node->left);    // 添加左节点（空节点不入栈）
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.top();    // 重新取出栈中元素
                st.pop();
                result.push_back(node->val); // 加入到结果集
            }
        }
        return result;
    }
};

1 2	if(node != NULL){ }else{}

注意该结构是标记法的核心体现
在if()中利用栈记录结点的处理顺序
在else{}则是标记的判断结果，可以进行处理

// 前序遍历
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                if (node->right) st.push(node->right);  // 右
                if (node->left) st.push(node->left);    // 左
                st.push(node);                          // 中
                st.push(NULL);
            } else {
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        return result;
    }
};

// 后序遍历

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                st.push(node);                          // 中
                st.push(NULL);

                if (node->right) st.push(node->right);  // 右
                if (node->left) st.push(node->left);    // 左

            } else {
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        return result;
    }
};

广度优先搜索与深度优先搜索在算法章节详细介绍

107 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值自底向上的层序遍历 ,（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

root = [3,9,20,null,null,15,7]

输出：[[15,7],[9,20],[3]]

广度优先搜索（层次遍历）


class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> vec;
        queue<TreeNode*> q;
        if(!root) return vec;
        q.push(root);
        while(!q.empty()){
            int size=q.size();
            vector<int> v;
            while(size--){
                TreeNode* temp=q.front();
                q.pop();
                if(temp&&temp->left) q.push(temp->left);
                if(temp&&temp->right) q.push(temp->right);
                v.push_back(temp->val);
            }
            vec.push_back(v);
        }
        reverse(vec.begin(),vec.end());
        return vec;
    }
};

深度优先搜索

199.二叉树的右视图

给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

我们对树进行深度优先搜索，在搜索过程中，我们总是先访问右子树。那么对于每一层来说，我们在这层见到的第一个结点一定是最右边的结点

并未涉及回溯

核心思想：使用栈，下一层最后一个入栈的为最右边元素，每层最先处理的即为最最右边元素

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        unordered_map<int, int> rightmostValueAtDepth;
        int max_depth = -1;

        stack<TreeNode*> nodeStack;
        stack<int> depthStack;
        nodeStack.push(root);
        depthStack.push(0);

        while (!nodeStack.empty()) {
            TreeNode* node = nodeStack.top();nodeStack.pop();
            int depth = depthStack.top();depthStack.pop();

            if (node != NULL) {
            	// 维护二叉树的最大深度
                max_depth = max(max_depth, depth);

                // 如果不存在对应深度的节点我们才插入
                if (rightmostValueAtDepth.find(depth) == rightmostValueAtDepth.end()) {
                    rightmostValueAtDepth[depth] =  node -> val;
                }

                nodeStack.push(node -> left);
                nodeStack.push(node -> right);
                depthStack.push(depth + 1);
                depthStack.push(depth + 1);
            }
        }

        vector<int> rightView;
        for (int depth = 0; depth <= max_depth; ++depth) {
            rightView.push_back(rightmostValueAtDepth[depth]);
        }

        return rightView;
    }
};

637. 二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
输入：root = [3,9,20,null,null,15,7]

输出：[3.00000,14.50000,11.00000]

解释：第 0 层的平均值为 3,

第 1 层的平均值为 14.5,

第 2 层的平均值为 11

因此返回 [3, 14.5, 11] 。

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        auto counts = vector<int>();
        auto sums = vector<double>();
        dfs(root, 0, counts, sums);
        auto averages = vector<double>();
        int size = sums.size();
        for (int i = 0; i < size; i++) {
            averages.push_back(sums[i] / counts[i]);
        }
        return averages;
    }

    void dfs(TreeNode* root, int level, vector<int> &counts, vector<double> &sums) {
        if (root == nullptr) {
            return;
        }
        if (level < sums.size()) {// 回溯部分
            sums[level] += root->val;
            counts[level] += 1;
        } else {
            sums.push_back(1.0 * root->val);
            counts.push_back(1);
        }
        dfs(root->left, level + 1, counts, sums);
        dfs(root->right, level + 1, counts, sums);
    }
};

翻转二叉树

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

思路：
可以发现想要翻转它，其实就把每一个节点的左右孩子交换一下就可以了。
关键在于遍历顺序，前中后序应该选哪一种遍历顺序？
遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果。
注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果
这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转了两次！建议拿纸画一画，就理解了

递归法

确定递归函数的参数和返回值
TreeNode* invertTree(TreeNode* root)
确定终止条件:当前节点为空的时候，就返回
if (root == NULL) return root;
确定单层递归的逻辑
因为是先前序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树。
1
2
3
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);

迭代法

栈替代递归迭代法（前序遍历）

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();              // 中
            st.pop();
            swap(node->left, node->right);
            if(node->right) st.push(node->right);   // 右
            if(node->left) st.push(node->left);     // 左
        }
        return root;
    }
};

遍历的统一迭代法

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                if (node->right) st.push(node->right);  // 右
                if (node->left) st.push(node->left);    // 左
                st.push(node);                          // 中
                st.push(NULL);
            } else {
                st.pop();
                node = st.top();
                st.pop();
                swap(node->left, node->right);          // 节点处理逻辑
            }
        }
        return root;
    }
};

广度优先遍历

也就是层序遍历，层数遍历也是可以翻转这棵树的，因为层序遍历也可以把每个节点的左右孩子都翻转一遍，代码如下

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                swap(node->left, node->right); // 节点处理
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return root;
    }
};

文中我指的是递归的中序遍历是不行的，因为使用递归的中序遍历，某些节点的左右孩子会翻转两次。

如果非要使用递归中序的方式写，也可以，如下代码就可以避免节点左右孩子翻转两次的情况：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        invertTree(root->left);         // 左
        swap(root->left, root->right);  // 中
        invertTree(root->left);         // 注意 这里依然要遍历左孩子，因为中间节点已经翻转了
        return root;
    }
};

对称二叉树

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。
输入：root = [1,2,2,3,4,4,3]
输出：true

思路判断对称二叉树要比较的是哪两个节点，要比较的可不是左右节点！
对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。

那么遍历的顺序应该是什么样的呢？

本题遍历只能是“后序遍历”，因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。

正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。

确定递归函数的参数和返回值
因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。

bool compare(TreeNode* left, TreeNode* right)

确定终止条件

if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false; // 注意这里我没有使用else

确定单层递归的逻辑

此时才进入单层递归的逻辑，单层递归的逻辑就是处理左右节点都不为空，且数值相同的情况。

比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
比较内测是否对称，传入左节点的右孩子，右节点的左孩子。
如果左右都对称就返回true ，有一侧不对称就返回false

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right) {
        // 首先排除空节点的情况
        if (left == NULL && right != NULL) return false;
        else if (left != NULL && right == NULL) return false;
        else if (left == NULL && right == NULL) return true;
        // 排除了空节点，再排除数值不相同的情况
        else if (left->val != right->val) return false;

        // 此时就是：左右节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
        bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
        bool inside = compare(left->right, right->left);    // 左子树：右、 右子树：左
        bool isSame = outside && inside;                    // 左子树：中、 右子树：中 （逻辑处理）
        return isSame;

    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};

迭代法

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        queue<TreeNode*> que;
        que.push(root->left);   // 将左子树头结点加入队列
        que.push(root->right);  // 将右子树头结点加入队列
        
        while (!que.empty()) {  // 接下来就要判断这两个树是否相互翻转
            TreeNode* leftNode = que.front(); que.pop();
            TreeNode* rightNode = que.front(); que.pop();
            if (!leftNode && !rightNode) {  // 左节点为空、右节点为空，此时说明是对称的
                continue;
            }

            // 左右一个节点不为空，或者都不为空但数值不相同，返回false
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                return false;
            }
            que.push(leftNode->left);   // 加入左节点左孩子
            que.push(rightNode->right); // 加入右节点右孩子
            que.push(leftNode->right);  // 加入左节点右孩子
            que.push(rightNode->left);  // 加入右节点左孩子
        }
        return true;
    }
};

相同二叉树以及另一棵树的子树

100. 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

相同二叉树的实现在对称二叉树的代码基础上改进即可

迭代

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<TreeNode*> que;
        if(p==nullptr&&q!=nullptr) return false;
        else if(p!=nullptr&q==nullptr) return false;
        else if(p==nullptr&&q==nullptr) return true;
        else if(p->val!=q->val) return false;

        que.push(p);
        que.push(q);

        while(!que.empty()){
            TreeNode* left_node=que.front();que.pop();
            TreeNode* right_node=que.front();que.pop();

            if(!left_node&&!right_node){
                continue;
            }

            if(!left_node||!right_node||(left_node->val!=right_node->val)){
                return false;
            }

            que.push(left_node->left);
            que.push(right_node->left);
            que.push(left_node->right);
            que.push(right_node->right);
        }
        return true;
    }
};

递归


 /**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p==nullptr&&q!=nullptr) return false;
        else if(p!=nullptr&&q==nullptr) return false;
        else if(p==nullptr&&q==nullptr) return true;
        else if(p->val!=q->val) return false;

        bool left_side=isSameTree(p->left,q->left);
        bool right_side=isSameTree(p->right,q->right);

        return left_side&&right_side;
    }
};

572. 另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

方法1：深度优先搜索暴力匹配

class Solution {
public:
    bool check(TreeNode *o, TreeNode *t) {
        if (!o && !t) {
            return true;
        }
        if ((o && !t) || (!o && t) || (o->val != t->val)) {
            return false;
        }
        return check(o->left, t->left) && check(o->right, t->right);
    }

    bool dfs(TreeNode *o, TreeNode *t) {
        if (!o) {
            return false;
        }
        return check(o, t) || dfs(o->left, t) || dfs(o->right, t);
    }

    bool isSubtree(TreeNode *s, TreeNode *t) {
        return dfs(s, t);
    }
};

时间复杂度：对于每一个s上的点，都需要做一次深度优先搜索来和 t 匹配，匹配一次的时间代价是 O(∣t∣)O(|t|)O(∣t∣)，那么总的时间代价就是 O(∣s∣×∣t∣)故渐进时间复杂度为 O(∣s∣×∣t∣)

空间复杂度：假设s深度为 ds, t的深度为dt,任意时刻栈空间的最大使用代价是 O(max⁡{ds,dt}),
故渐进空间复杂度为 O(max⁡{ds,dt})

方法2：深度优先搜索序列上做串匹配（KMP）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void dfsOrder(TreeNode* node,string& str){
        if(node==nullptr) return;
        str+="#"+to_string(node->val)+"#";
        if(node->left){
            dfsOrder(node->left,str);
        }else{
            str+='@';
        }

        if(node->right){
            dfsOrder(node->right,str);
        }else{
            str+='@';
        }


    }
    bool kmp(string source_str,string dst_str){
        int j=-1;
        int next_val[dst_str.size()];
        next_val[0]=j;

        for(int i=1;i<dst_str.size();++i){
            while(j>=0&&dst_str[i]!=dst_str[j+1]){
                j=next_val[j];
            }
            if(dst_str[i]==dst_str[j+1]){
                ++j;
            }
            next_val[i]=j;
        }

        j=-1;
        for(int i=0;i<source_str.size();++i){
            while(j>=0&&source_str[i]!=dst_str[j+1]){
                j=next_val[j];
            }
            if(source_str[i]==dst_str[j+1]){
                ++j;
            }
            if(j==dst_str.size()-1){
                return true;
            }
        }
        return false;
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {

        string root_str="",subRoot_str="";
        dfsOrder(root,root_str);
        dfsOrder(subRoot,subRoot_str);
        cout<<root_str<<endl;
        cout<<subRoot_str<<endl;
        return kmp(root_str,subRoot_str);
    }

};

时间复杂度：深度搜索序列的时间代价是 O(∣s∣+∣t∣) KMP进行串匹配O(∣s∣+∣t∣

空间复杂度： O(∣s∣+∣t∣)

方法3 ：树哈希法

考虑把每个子树都映射成一个唯一的数，如果 t对应的数字和 s中任意一个子树映射的数字相等，则 ttt 是 s的某一棵子树。如何映射呢？我们可以定义这样的哈希函数：

fo=vo+31⋅fl⋅p(sl)+179⋅fr⋅p(sr)

这里 fx表示节点 x的哈希值，sx表示节点 x对应的子树大小，vx代表节点 x的 val，p(n) 表示第 n 个素数，o表示当前节点，l和 r分别表示左右孩子。这个式子的意思是：当前节点 o的哈希值等于这个点的 val 加上 31左子树的哈希值乘以第 sl个素数，再加上 179倍右子树的哈希值乘以第 sr个素数。这里的 31和 179这两个数字只是为了区分左右子树，你可以自己选择你喜欢的权值。

欧拉筛法求素数

#include <iostream>
#include <cstring>

using namespace std;

const int maxn = 100;
bool isprime[maxn+1];
int primetable[maxn+1], ptr;

void mktable()
{
    ptr = 0;
    memset(isprime,true,sizeof isprime);
    for (int i=2; i<=maxn; i++)
    {
        if (isprime[i] == true)
            primetable[ptr++] = i;
        for (int j=0; j<ptr&&i*primetable[j]<=maxn; j++)
        {
            isprime[i*primetable[j]] = false;
            if (i%primetable[j] == 0)
                break;
        }
    }
}

int main()
{
    mktable();
    for(int i=0; i<ptr; i++)
        cout << primetable[i] << ' ';
    return 0;
}

class Solution {
public:
    static constexpr int MAX_N = 1000 + 5;
    static constexpr int MOD = int(1E9) + 7;

    bool vis[MAX_N];
    int p[MAX_N], tot;
    void getPrime() {
        vis[0] = vis[1] = 1; tot = 0;
        for (int i = 2; i < MAX_N; ++i) {
            if (!vis[i]) p[++tot] = i;
            for (int j = 1; j <= tot && i * p[j] < MAX_N; ++j) {
                vis[i * p[j]] = 1;
                if (i % p[j] == 0) break;
            }
        }
    }

    struct Status {
        int f, s; // f 为哈希值 | s 为子树大小
        Status(int f_ = 0, int s_ = 0) 
            : f(f_), s(s_) {}
    };

    unordered_map <TreeNode *, Status> hS, hT;

    void dfs(TreeNode *o, unordered_map <TreeNode *, Status> &h) {
        h[o] = Status(o->val, 1);
        if (!o->left && !o->right) return;
        if (o->left) {
            dfs(o->left, h);
            h[o].s += h[o->left].s;
            h[o].f = (h[o].f + (31LL * h[o->left].f * p[h[o->left].s]) % MOD) % MOD;
        }
        if (o->right) {
            dfs(o->right, h);
            h[o].s += h[o->right].s;
            h[o].f = (h[o].f + (179LL * h[o->right].f * p[h[o->right].s]) % MOD) % MOD;
        }
    }

    bool isSubtree(TreeNode* s, TreeNode* t) {
        getPrime();
        dfs(s, hS);
        dfs(t, hT);

        int tHash = hT[t].f;
        for (const auto &[k, v]: hS) {
            if (v.f == tHash) {
                return true;
            }
        } 

        return false;
    }
};

二叉树的最小深度

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
输入：root = [3,9,20,null,null,15,7]
输出：2

思路·：

常规方法考虑广度优先搜索（层次遍历）
参考最大深度的递归求法，考虑当前节点只有单一分支的情况

class Solution {
public:
    int getDepth(TreeNode* node) {
        if (node == NULL) return 0;
        int leftDepth = getDepth(node->left);           // 左
        int rightDepth = getDepth(node->right);         // 右
                                                        // 中
        // 当一个左子树为空，右不为空，这时并不是最低点
        if (node->left == NULL && node->right != NULL) { 
            return 1 + rightDepth;
        }   
        // 当一个右子树为空，左不为空，这时并不是最低点
        if (node->left != NULL && node->right == NULL) { 
            return 1 + leftDepth;
        }
        int result = 1 + min(leftDepth, rightDepth);
        return result;
    }

    int minDepth(TreeNode* root) {
        return getDepth(root);
    }
};

写法二

class Solution {
public:
    int minDepth(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }

        if (root->left == nullptr && root->right == nullptr) {
            return 1;
        }

        int min_depth = INT_MAX;
        if (root->left != nullptr) {
            min_depth = min(minDepth(root->left), min_depth);
        }
        if (root->right != nullptr) {
            min_depth = min(minDepth(root->right), min_depth);
        }

        return min_depth + 1;
    }
};

求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。

完全二叉的节点个数

222. 完全二叉树的节点个数

给你一棵完全二叉树的根节点 root ，求出该树的节点个数。
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h 个节点。

思路：

常规的递归或者利用层序遍历迭代
$O(\log n × \log n)$时间复杂度的的

完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        int leftHeight = 0, rightHeight = 0; // 这里初始为0是有目的的，为了下面求指数方便
        while (left) {  // 求左子树深度
            left = left->left;
            leftHeight++;
        }
        while (right) { // 求右子树深度
            right = right->right;
            rightHeight++;
        }
        if (leftHeight == rightHeight) {
            return (2 << leftHeight) - 1; // 注意(2<<1) 相当于2^2，所以leftHeight初始为0
        }
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

平衡二叉树

110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1

自底向上递归

int dfs(TreeNode* node){
    if(node==nullptr) return 0;
    int depf=dfs(node->left);
    if(depf==-1) return -1;
    int depr=dfs(node->right);
    if(depr==-1) return -1;
    return abs(depr-depf)>1?-1:1+max(depf,depr);
        
}
bool isBalanced(TreeNode* root) {
   return dfs(root)!=-1?true:false;
}

对于有返回值类型的情况也可以遍历整棵树

自顶向下递归

class Solution {
public:
    int height(TreeNode* root) {
        if (root == NULL) {
            return 0;
        } else {
            return max(height(root->left), height(root->right)) + 1;
        }
    }

    bool isBalanced(TreeNode* root) {
        if (root == NULL) {
            return true;
        } else {
            return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
        }
    }
};

求深度与求高度问题

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

求二叉树最大深度迭代法（前序遍历）

class Solution {
public:
    int result;
    void getDepth(TreeNode* node, int depth) {
        result = depth > result ? depth : result; // 中

        if (node->left == NULL && node->right == NULL) return ;

        if (node->left) { // 左
            depth++;    // 深度+1
            getDepth(node->left, depth);
            depth--;    // 回溯，深度-1
        }
        if (node->right) { // 右
            depth++;    // 深度+1
            getDepth(node->right, depth);
            depth--;    // 回溯，深度-1
        }
        return ;
    }
    int maxDepth(TreeNode* root) {
        result = 0;
        if (root == NULL) return result;
        getDepth(root, 1);
        return result;
    }
};

相当于

 class Solution {
public:
    int result;
    void getDepth(TreeNode* node, int depth) {
        result = depth > result ? depth : result; // 中
        if (node->left == NULL && node->right == NULL) return ;
        if (node->left) { // 左
            getDepth(node->left, depth + 1);
        }
        if (node->right) { // 右
            getDepth(node->right, depth + 1);
        }
        return ;
    }
    int maxDepth(TreeNode* root) {
        result = 0;
        if (root == 0) return result;
        getDepth(root, 1);
        return result;
    }
};

第一个版本的代码更容易体现回溯的过程

本题解题思路
注意理解本题中递归实现的返回值

明确递归函数的参数和返回值

参数：当前传入节点。
返回值：以当前传入节点为根节点的树的高度
那么如何标记左右子树是否差值大于1呢？
如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。
所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。

1 2	// -1 表示已经不是平衡二叉树了，否则返回值是以该节点为根节点树的高度 int getHeight(TreeNode* node)

明确终止条件

递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0

1
2
3

if (node == NULL) {
    return 0;
}

明确单层递归的逻辑

分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则则返回-1，表示已经不是二叉平衡树了

class Solution {
public:
    // 返回以该节点为根节点的二叉树的高度，如果不是二叉搜索树了则返回-1
    int getHeight(TreeNode* node) {
        if (node == NULL) {
            return 0;
        }
        int leftHeight = getHeight(node->left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(node->right);
        if (rightHeight == -1) return -1;
        return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
    }
    bool isBalanced(TreeNode* root) {
        return getHeight(root) == -1 ? false : true;
    }
};

注意:若递归函数的返回值为bool类型，则无法记录以当前节点为根的子树的高度；

本题如果采用迭代实现

可以先定义一个函数，专门用来求高度。
然后再用栈来模拟前序遍历，遍历每一个节点的时候，再去判断左右孩子的高度是否符合

class Solution {
private:
    int getDepth(TreeNode* cur) {
        stack<TreeNode*> st;
        if (cur != NULL) st.push(cur);
        int depth = 0; // 记录深度
        int result = 0;
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                st.push(node);                          // 中
                st.push(NULL);
                depth++;
                if (node->right) st.push(node->right);  // 右
                if (node->left) st.push(node->left);    // 左

            } else {
                st.pop();
                node = st.top();
                st.pop();
                depth--;
            }
            result = result > depth ? result : depth;
        }
        return result;
    }

public:
    bool isBalanced(TreeNode* root) {
        stack<TreeNode*> st;
        if (root == NULL) return true;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                       // 中
            st.pop();
            if (abs(getDepth(node->left) - getDepth(node->right)) > 1) {
                return false;
            }
            if (node->right) st.push(node->right);           // 右（空节点不入栈）
            if (node->left) st.push(node->left);             // 左（空节点不入栈）
        }
        return true;
    }
};

当然此题用迭代法，其实效率很低，因为没有很好的模拟回溯的过程，所以迭代法有很多重复的计算。

虽然理论上所有的递归都可以用迭代来实现，但是有的场景难度可能比较大。

例如：都知道回溯法其实就是递归，但是很少人用迭代的方式去实现回溯算法！

因为对于回溯算法已经是非常复杂的递归了，如果在用迭代的话，就是自己给自己找麻烦，效率也并不一定高。

二叉树的所有路径

257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按任意顺序，返回所有从根节点到叶子节点的路径。
叶子节点是指没有子节点的节点。

递归

递归函数函数参数以及返回值
要传入根节点，记录每一条路径的path，和存放结果集的result，这里递归不需要返回值
void traversal(TreeNode* cur, vector<int>& path, vector<string>& result)

确定递归终止条件

1
2
3

if (cur->left == NULL && cur->right == NULL) {
        终止处理逻辑
}

if (cur->left == NULL && cur->right == NULL) { // 遇到叶子节点
    string sPath;
    for (int i = 0; i < path.size() - 1; i++) { // 将path里记录的路径转为string格式
        sPath += to_string(path[i]);
        sPath += "->";
    }
    sPath += to_string(path[path.size() - 1]); // 记录最后一个节点（叶子节点）
    result.push_back(sPath); // 收集一个路径
    return;
}

确定单层递归逻辑
回溯和递归是一一对应的，有一个递归，就要有一个回溯

class Solution {
private:

    void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
        path.push_back(cur->val);
        // 这才到了叶子节点
        if (cur->left == NULL && cur->right == NULL) {
            string sPath;
            for (int i = 0; i < path.size() - 1; i++) {
                sPath += to_string(path[i]);
                sPath += "->";
            }
            sPath += to_string(path[path.size() - 1]);
            result.push_back(sPath);
            return;
        }
        if (cur->left) {
            traversal(cur->left, path, result);
            path.pop_back(); // 回溯
        }
        if (cur->right) {
            traversal(cur->right, path, result);
            path.pop_back(); // 回溯
        }
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;
    }
};

精简版代码

class Solution {
private:

    void traversal(TreeNode* cur, string path, vector<string>& result) {
        path += to_string(cur->val); // 中
        if (cur->left == NULL && cur->right == NULL) {
            result.push_back(path);
            return;
        }
        if (cur->left) traversal(cur->left, path + "->", result); // 左
        if (cur->right) traversal(cur->right, path + "->", result); // 右
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;

    }
};

注意在函数定义的时候void traversal(TreeNode* cur, string path, vector<string>& result) ，定义的是string path，每次都是复制赋值，不用使用引用，否则就无法做到回溯的效果

迭代法

至于非递归的方式，我们可以依然可以使用前序遍历的迭代方式来模拟遍历路径的过程，递归能做的，栈也能做！


class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        stack<TreeNode*> treeSt;// 保存树的遍历节点
        stack<string> pathSt;   // 保存遍历路径的节点
        vector<string> result;  // 保存最终路径集合
        if (root == NULL) return result;
        treeSt.push(root);
        pathSt.push(to_string(root->val));
        while (!treeSt.empty()) {
            TreeNode* node = treeSt.top(); treeSt.pop(); // 取出节点 中
            string path = pathSt.top();pathSt.pop();    // 取出该节点对应的路径
            if (node->left == NULL && node->right == NULL) { // 遇到叶子节点
                result.push_back(path);
            }
            if (node->right) { // 右
                treeSt.push(node->right);
                pathSt.push(path + "->" + to_string(node->right->val));
            }
            if (node->left) { // 左
                treeSt.push(node->left);
                pathSt.push(path + "->" + to_string(node->left->val));
            }
        }
        return result;
    }
};

递归函数中自定义参数和全局变量，参数与参数引用区别

在一棵树上求目标值为target的路径，对于参数有这样集中应用情况

1.全局变量记录当前路径之和sum，存储当前节点的vector也可以当成全局变量
我们每一次都是改变的这个全局变量，所以当我们遍历到最后时，不符合要求的时候，都要把路径上计算过的值和结点一并抛出pop和–，当然对于参数中存在引用来说也是同样道理，
因为引用其实就相当于直接改变这个数，而普通的传值参数只会开辟新的空间，而不改变上一个递归函数的值，所以在这方面上来说，引用和全局变量没什么区别

//引用的处理过程  
void helper(TreeNode *root,int target,vector<vector<int>>&res,vector<int>&temp)
{
    if(root==NULL)
        return;
    temp.push_back(root->val);
    if(!root->left&&!root->right&&target-root->val==0){
            res.push_back(temp);
        }
            
    helper(root->left,target-root->val,res,temp);
    helper(root->right,target-root->val,res,temp);

    temp.pop_back();

}

两个数组都是引用，直接改变他们自身，target为传值，这一时刻改变值不会影响上一刻大小，因为这是两个不同的空间，在函数调用的时候，
只不过把当前空间的变量复制，然后用这个复制的值来进行下一时刻的递归调用

//全局变量的处理过程
int currentSum = 0;  
vector<Node*> path;
 
void traverse(Node *root, int expectedNum) {
    if(root==NULL) return;
 
    currentSum += root->value;  
    path.push_back(root);  
    //如果是叶节点，并且路径上结点的和等于输入的值  
    if(root->left == NULL && root->right == NULL) {  
        if(currentSum == expectedNum) {  
            show(path);  
            cout << currentSum <<endl;  
        }  
    }  
 
    traverse(root->left, expectedNum);  
    traverse(root->right, expectedNum);  
 
    currentSum -= root->value;   // 必须恢复，所有函数调用使用同一个值  
    path.pop_back();[/color]  
}

2.函数内定义的变量和下一次递归调用的同名变量是不一样的，经过层层调用的递归函数，在其内部的自定义变量互不影响，因为他们在栈中的地址是不同的，
由栈顶逐渐移步到栈底，上一时刻既不能影响下一刻，下一刻也不能影响上一刻，除非有return，注意return的是这个变量的复制体，而不是本身，
因为本身在函数运行结束完之后，也就随之结束，所以就不能用引用，也不能返回引用，只能返回值
那么定义自变量大部分函数为了能够承接下一时刻的返回值作为衔接，这个值可以通过函数传递到下一时刻

3.普通的函数参数，其实这种就和在函数内部参数一样，

void traverse(Node *root, int currentSum, vector<Node *> path, int expectedNum) {
    if(root==NULL) return;
 
    currentSum += root->value;  
    path.push_back(root);  
    //如果是叶节点，并且路径上结点的和等于输入的值  
    if(root->left == NULL && root->right == NULL) {  
        if(currentSum == expectedNum) {  
            show(path);  
            cout << currentSum <<endl;  
        }  
    }  
 
    traverse(root->left, currentSum, path, expectedNum);  
    traverse(root->right, currentSum, path, expectedNum);  
 
    // 不必恢复  currentSum, path，各函数调用层独立使用  
}

二叉树左叶子节点之和

给定二叉树的根节点 root ，返回所有左叶子之和。

404. 左叶子之和

确定递归函数的参数和返回值
判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和，所以为int
使用题目中给出的函数就可以了。
确定终止条件
if (root == NULL) return 0;
很容易误写成 if(root->left==nullptr&&root->right==nullptr){ return root->val; }
区别递归的终止条件与递归单层返回值

确定单层递归的逻辑
当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和右子树左叶子之和，相加便是整个树的左叶子之和。
关键在于左叶子节点的判断与处理

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;

        int leftValue = sumOfLeftLeaves(root->left);    // 左
        int rightValue = sumOfLeftLeaves(root->right);  // 右
                                                        // 中
        int midValue = 0;
        if (root->left && !root->left->left && !root->left->right) { // 中
            midValue = root->left->val;
        }
        int sum = midValue + leftValue + rightValue;
        return sum;
    }
};

找树左下角节点值

给定一个二叉树的根节点 root，请找出该二叉树的最底层最左边节点的值。
假设二叉树中至少有一个节点。

513. 找树左下角的值

确定递归函数的参数和返回值
参数必须有要遍历的树的根节点，还有就是一个int型的变量用来记录最长深度。这里就不需要返回值了，所以递归函数的返回类型为void。
本题还需要类里的两个全局变量，maxLen用来记录最大深度，maxleftValue记录最大深度最左节点的数值。
1
2
3
int maxLen = INT_MIN; // 全局变量记录最大深度
int maxleftValue; // 全局变量最大深度最左节点的数值
void traversal(TreeNode* root, int leftLen)
如果需要遍历整棵树，递归函数就不能有返回值。如果需要遍历某一条固定路线，递归函数就一定要有返回值！
上题中求左叶子节点之和，就是沿着固定的路线搜索
确定终止条件
当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度。

if (root->left == NULL && root->right == NULL) {
    if (leftLen > maxLen) {
        maxLen = leftLen;           // 更新最大深度
        maxleftValue = root->val;   // 最大深度最左面的数值
    }
    return;
}

确定单层递归的逻辑
在找最大深度的时候，递归的过程中依然要使用回溯，代码如下：

class Solution {
public:
    int maxLen = INT_MIN;
    int maxleftValue;
    void traversal(TreeNode* root, int leftLen) {
        if (root->left == NULL && root->right == NULL) {
            if (leftLen > maxLen) {
                maxLen = leftLen;
                maxleftValue = root->val;
            }
            return;
        }
        if (root->left) {
            leftLen++;
            traversal(root->left, leftLen);
            leftLen--; // 回溯
        }
        if (root->right) {
            leftLen++;
            traversal(root->right, leftLen);
            leftLen--; // 回溯
        }
        return;
    }
    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return maxleftValue;
    }
};

路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。

112. 路径总和

确定递归函数的参数和返回类型
参数：需要二叉树的根节点，还需要一个计数器，这个计数器用来计算二叉树的一条边之和是否正好是目标和，计数器为int型。
再来看返回值，递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：
- 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）
- 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。（这种情况我们在236. 二叉树的最近公共祖先
- 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）

bool traversal(treenode* cur, int count) // 注意函数的返回类型

确定终止条件
首先计数器如何统计这一条路径的和呢？
不要去累加然后判断是否等于目标和，那么代码比较麻烦，可以用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。
如果最后count == 0，同时到了叶子节点的话，说明找到了目标和。
如果遍历到了叶子节点，count不为0，就是没找到。
递归终止条件代码如下:

if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
if (!cur->left && !cur->right) return false; // 遇到叶子节点而没有找到合适的边，直接返回

确定单层递归的逻辑

因为终止条件是判断叶子节点，所以递归的过程中就不要让空节点进入递归了
与终止条件是空节点不同
递归函数是有返回值的，如果递归函数返回true，说明找到了合适的路径，应该立刻返回

class solution {
private:
    bool traversal(treenode* cur, int count) {
        if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
        if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回

        if (cur->left) { // 左 （空节点不遍历）
            count -= cur->left->val; // 递归，处理节点;
            if (traversal(cur->left, count)) return true;
            count += cur->left->val; // 回溯，撤销处理结果
        }
        if (cur->right) { // 右 （空节点不遍历）
            count -= cur->right->val; // 递归，处理节点;
            if (traversal(cur->right, count)) return true;
            count += cur->right->val; // 回溯，撤销处理结果
        }
        return false;
    }

public:
    bool haspathsum(treenode* root, int sum) {
        if (root == null) return false;
        return traversal(root, sum - root->val);
    }
};

从中序与后序遍历序列构造二叉树

106. 从中序与后序遍历序列构造二叉树

思路：
找到根节点，将序列切割成左子树序列与右子树序列，然后递归处理

class Solution {
private:
    TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size() == 0) return NULL;

        // 后序遍历数组最后一个元素，就是当前的中间节点
        int rootValue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootValue);

        // 叶子节点
        if (postorder.size() == 1) return root;

        // 找到中序遍历的切割点
        int delimiterIndex;
        for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }

        // 切割中序数组
        // 左闭右开区间：[0, delimiterIndex)
        vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
        // [delimiterIndex + 1, end)
        vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );

        // postorder 舍弃末尾元素
        postorder.resize(postorder.size() - 1);

        // 切割后序数组
        // 依然左闭右开，注意这里使用了左中序数组大小作为切割点
        // [0, leftInorder.size)
        vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
        // [leftInorder.size(), end)
        vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());

        root->left = traversal(leftInorder, leftPostorder);
        root->right = traversal(rightInorder, rightPostorder);

        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder, postorder);
    }
};

优化

 class Solution {
private:
    // 中序区间：[inorderBegin, inorderEnd)，后序区间[postorderBegin, postorderEnd)
    TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {
        if (postorderBegin == postorderEnd) return NULL;

        int rootValue = postorder[postorderEnd - 1];
        TreeNode* root = new TreeNode(rootValue);

        if (postorderEnd - postorderBegin == 1) return root;

        int delimiterIndex;
        for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }
        // 切割中序数组
        // 左中序区间，左闭右开[leftInorderBegin, leftInorderEnd)
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimiterIndex;
        // 右中序区间，左闭右开[rightInorderBegin, rightInorderEnd)
        int rightInorderBegin = delimiterIndex + 1;
        int rightInorderEnd = inorderEnd;

        // 切割后序数组
        // 左后序区间，左闭右开[leftPostorderBegin, leftPostorderEnd)
        int leftPostorderBegin =  postorderBegin;
        int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
        // 右后序区间，左闭右开[rightPostorderBegin, rightPostorderEnd)
        int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);
        int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素，已经作为节点了

        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  postorder, leftPostorderBegin, leftPostorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);

        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        // 左闭右开的原则
        return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
};

相似题
654. 最大二叉树

给定一个不重复的整数数组 nums 。最大二叉树可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的最大二叉树。

105. 从前序与中序遍历序列构造二叉树

合并二叉树

617. 合并二叉树

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

思路：
递归求解二叉树的问题，一定要先考虑二叉树的遍历顺序

**由于是构造二叉树，可以考虑基于原来的二叉树构造，减少所用内存空间 **

确定递归函数的参数和返回值：

首先那么要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
确定终止条件：

因为是传入了两个树，那么就有两个树遍历的节点t1 和 t2，如果t1 == NULL 了，两个树合并就应该是 t2 了啊（如果t2也为NULL也无所谓，合并之后就是NULL）。

反过来如果t2 == NULL，那么两个数合并就是t1（如果t1也为NULL也无所谓，合并之后就是NULL）。
if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2
if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1
确定单层递归的逻辑：
单层递归的逻辑就比较好些了，这里我们用重复利用一下t1这个树，t1就是合并之后树的根节点（就是修改了原来树的结构）
那么单层递归中，就要把两棵树的元素加到一起。

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2
        if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1
        // 修改了t1的数值和结构
        t1->val += t2->val;                             // 中
        t1->left = mergeTrees(t1->left, t2->left);      // 左
        t1->right = mergeTrees(t1->right, t2->right);   // 右
        return t1;
    }
};

二叉搜索树

验证二叉搜索树

98. 验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

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

思维误区：递归的判断左子树<根节点<右子树节点
没能考虑到右子树某个节点小于根节点等情况
我们要比较的是左子树所有节点小于中间节点，右子树所有节点大于中间节点

思路：

对于二叉树的问题，应该从遍历方式的角度入手，本题只要验证中序遍历顺序为递增序列即可

class Solution {
public:
    TreeNode* pre = NULL; // 用来记录前一个节点
    bool isValidBST(TreeNode* root) {
        if (root == NULL) return true;
        bool left = isValidBST(root->left);

        if (pre != NULL && pre->val >= root->val) return false;
        pre = root; // 记录前一个节点

        bool right = isValidBST(root->right);
        return left && right;
    }
};

注意递归中记录前一个节点的指针的技巧

迭代法

class Solution {
public:
    bool isValidBST(TreeNode* root) { 
        if(root==nullptr) return true;
        stack<TreeNode*> st;
        st.push(root);
        TreeNode* pre=nullptr;
        while(st.size()>0){
            TreeNode* node=st.top();
            
            if(node!=nullptr){
                st.pop();
                if(node->right) st.push(node->right);
                st.push(node);
                st.push(nullptr);
                if(node->left) st.push(node->left);
            }
            else{
                st.pop();
                node=st.top();
                if(pre!=nullptr&&pre->val>=node->val) return false;
                pre=node;
                st.pop();
            }
        }
        return true;
    }
};

总结

遇到在二叉搜索树上求什么最值，求差值之类的，都要思考一下二叉搜索树可是有序的，要利用好这一特点。

同时要学会在递归遍历的过程中如何记录前后两个指针，这也是一个小技巧，学会了还是很受用的。

二叉搜索树中的众数

501. 二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按任意顺序返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

如果对于一般的二叉树，考虑使用map统计频率，C++中如果使用std::map或者std::multimap可以对key排序，但不能对value排序。

所以要把map转化数组即vector，再进行排序，当然vector里面放的也是pair<int, int>类型的数据，第一个int为元素，第二个int为出现频率。

class Solution {
private:

void searchBST(TreeNode* cur, unordered_map<int, int>& map) { // 前序遍历
    if (cur == NULL) return ;
    map[cur->val]++; // 统计元素频率
    searchBST(cur->left, map);
    searchBST(cur->right, map);
    return ;
}
bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {
    return a.second > b.second;
}
public:
    vector<int> findMode(TreeNode* root) {
        unordered_map<int, int> map; // key:元素，value:出现频率
        vector<int> result;
        if (root == NULL) return result;
        searchBST(root, map);
        vector<pair<int, int>> vec(map.begin(), map.end());
        sort(vec.begin(), vec.end(), cmp); // 给频率排个序
        result.push_back(vec[0].first);
        for (int i = 1; i < vec.size(); i++) {
            // 取最高的放到result数组中
            if (vec[i].second == vec[0].second) result.push_back(vec[i].first);
            else break;
        }
        return result;
    }
};

对于二叉搜索树，可以充分利用中序遍历的特点

前一个节点pre的记录
如果计数count和最大值相同，放进result中
如果计数大于最大值频率，清空result

class Solution {
private:
    int maxCount; // 最大频率
    int count; // 统计频率
    TreeNode* pre;
    vector<int> result;
    void searchBST(TreeNode* cur) {
        if (cur == NULL) return ;

        searchBST(cur->left);       // 左
                                    // 中
        if (pre == NULL) { // 第一个节点
            count = 1;
        } else if (pre->val == cur->val) { // 与前一个节点数值相同
            count++;
        } else { // 与前一个节点数值不同
            count = 1;
        }
        pre = cur; // 更新上一个节点

        if (count == maxCount) { // 如果和最大值相同，放进result中
            result.push_back(cur->val);
        }

        if (count > maxCount) { // 如果计数大于最大值频率
            maxCount = count;   // 更新最大频率
            result.clear();     // 很关键的一步，不要忘记清空result，之前result里的元素都失效了
            result.push_back(cur->val);
        }

        searchBST(cur->right);      // 右
        return ;
    }

public:
    vector<int> findMode(TreeNode* root) {
        count = 0;
        maxCount = 0;
        TreeNode* pre = NULL; // 记录前一个节点
        result.clear();

        searchBST(root);
        return result;
    }
};

二叉树的最近公共祖先

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路：

处理二叉树问题，首先思考遍历顺序，本题需要能自底向上查找，二叉树回溯的过程就是从低到上，后序遍历就是天然的回溯过程；

首先最容易想到的一个情况：如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。

但是很多人容易忽略一个情况，就是节点本身p(q)，它拥有一个子孙节点q(p)。

但是如果p或者q本身就是最近公共祖先呢？其实只需要找到一个节点是p或者q的时候，直接返回当前节点，无需继续递归子树。如果接下来的遍历中找到了后继节点满足第一种情况则修改返回值为后继节点，否则，继续返回已找到的节点即可。

递归三部曲

确定递归函数返回值以及参数

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
确定终止条件

if (root == q || root == p || root == NULL) return root;
确定单层递归逻辑

值得注意的是本题函数有返回值，是因为回溯的过程需要递归函数的返回值做判断，但本题我们依然要遍历树的所有节点。

如果递归函数有返回值，如何区分要搜索一条边，还是搜索整个树呢？

搜索一条边的写法：

if (递归函数(root->left)) return ;

if (递归函数(root->right)) return ;

搜索整个树写法：

left = 递归函数(root->left);

right = 递归函数(root->right);

left与right的逻辑处理;

在递归函数有返回值的情况下：如果要搜索一条边，递归函数返回值不为空的时候，立刻返回，

如果搜索整个树，直接用一个变量left、right接住返回值，这个left、right后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）

TreeNode* left = lowestCommonAncestor(root->left, p, q);

TreeNode* right = lowestCommonAncestor(root->right, p, q);

结合递归终止条件可以知道，如果left 和 right都不为空，说明此时root就是最近公共节点。这个比较好理解

如果left为空，right不为空，就返回right，说明目标节点是通过right返回的，反之依然。

推理一下节点的返回过程加强理解

if (left == NULL && right != NULL) return right;
else if (left != NULL && right == NULL) return left;
else  { //  (left == NULL && right == NULL)
    return NULL;
}

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == q || root == p || root == NULL) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left != NULL && right != NULL) return root;

        if (left == NULL && right != NULL) return right;
        else if (left != NULL && right == NULL) return left;
        else  { //  (left == NULL && right == NULL)
            return NULL;
        }

    }
};

二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路：

考虑到二叉搜索树的特点，本题递归求解可以可以搜索一条边的方法,在这里调用递归函数的地方，把递归函数的返回值left，直接return

class Solution {
private:
    TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {
        if (cur == NULL) return cur;
                                                        // 中
        if (cur->val > p->val && cur->val > q->val) {   // 左
            TreeNode* left = traversal(cur->left, p, q);
            if (left != NULL) {
                return left;
            }
        }

        if (cur->val < p->val && cur->val < q->val) {   // 右
            TreeNode* right = traversal(cur->right, p, q);
            if (right != NULL) {
                return right;
            }
        }
        return cur;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return traversal(root, p, q);
    }
};

简洁版

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root->val > p->val && root->val > q->val) {
            return lowestCommonAncestor(root->left, p, q);
        } else if (root->val < p->val && root->val < q->val) {
            return lowestCommonAncestor(root->right, p, q);
        } else return root;
    }
};

迭代法

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root) {
            if (root->val > p->val && root->val > q->val) {
                root = root->left;
            } else if (root->val < p->val && root->val < q->val) {
                root = root->right;
            } else return root;
        }
        return NULL;
    }
};

二叉搜索树节点的插入

701. 二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。

思路：

只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了。

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == NULL) {
            TreeNode* node = new TreeNode(val);
            return node;
        }
        if (root->val > val) root->left = insertIntoBST(root->left, val);
        if (root->val < val) root->right = insertIntoBST(root->right, val);
        return root;
    }
};

在王道中二叉排序树插入如下：

基于二叉搜索树的插入可以实现二叉搜索树的构造

删除二叉搜索树中的节点

450. 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

思路：

关键在于处理单层递归逻辑中各种节点的删除情况：

第一种情况：没找到删除的节点，遍历到空节点直接返回了

找到删除的节点

第二种情况：左右孩子都为空（叶子节点），直接删除节点，返回NULL为根节点

第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点

第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点

第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

if (root->val == key) {
    // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
    // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
    if (root->left == nullptr) return root->right;
    // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
    else if (root->right == nullptr) return root->left;
    // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
    // 并返回删除节点右孩子为新的根节点。
    else {
        TreeNode* cur = root->right; // 找右子树最左面的节点
        while(cur->left != nullptr) {
            cur = cur->left;
        }
        cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置
        TreeNode* tmp = root;   // 把root节点保存一下，下面来删除
        root = root->right;     // 返回旧root的右孩子作为新root
        delete tmp;             // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）
        return root;
    }
}

这里相当于把新的节点返回给上一层，上一层就要用 root->left 或者 root->right接住，代码如下：

1
2
3

if (root->val > key) root->left = deleteNode(root->left, key);
if (root->val < key) root->right = deleteNode(root->right, key);
return root;

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
        if (root->val == key) {
            // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
            if (root->left == nullptr && root->right == nullptr) {
                ///! 内存释放
                delete root;
                return nullptr;
            }
            // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
            else if (root->left == nullptr) {
                auto retNode = root->right;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
            else if (root->right == nullptr) {
                auto retNode = root->left;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
            // 并返回删除节点右孩子为新的根节点。
            else {
                TreeNode* cur = root->right; // 找右子树最左面的节点
                while(cur->left != nullptr) {
                    cur = cur->left;
                }
                cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置
                TreeNode* tmp = root;   // 把root节点保存一下，下面来删除
                root = root->right;     // 返回旧root的右孩子作为新root
                delete tmp;             // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）
                return root;
            }
        }
        if (root->val > key) root->left = deleteNode(root->left, key);
        if (root->val < key) root->right = deleteNode(root->right, key);
        return root;
    }
};

修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在唯一的答案。

669. 修剪二叉搜索树

单层递归逻辑

如果root（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点。

if (root->val < low) {
    TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点
    return right;
}

如果root(当前节点)的元素大于high的，那么应该递归左子树，并返回左子树符合条件的头结点。

if (root->val > high) {
    TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点
    return left;
}

接下来要将下一层处理完左子树的结果赋给root->left，处理完右子树的结果赋给root->right

1
2
3

root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子
root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子
return root;

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == nullptr ) return nullptr;
        if (root->val < low) {
            TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点
            return right;
        }
        if (root->val > high) {
            TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点
            return left;
        }
        root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子
        root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子
        return root;
    }
};

迭代法

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int L, int R) {
        if (!root) return nullptr;

        // 处理头结点，让root移动到[L, R] 范围内，注意是左闭右闭
        while (root != nullptr && (root->val < L || root->val > R)) {
            if (root->val < L) root = root->right; // 小于L往右走
            else root = root->left; // 大于R往左走
        }
        TreeNode *cur = root;
        // 此时root已经在[L, R] 范围内，处理左孩子元素小于L的情况
        while (cur != nullptr) {
            while (cur->left && cur->left->val < L) {
                cur->left = cur->left->right;
            }
            cur = cur->left;
        }
        cur = root;

        // 此时root已经在[L, R] 范围内，处理右孩子大于R的情况
        while (cur != nullptr) {
            while (cur->right && cur->right->val > R) {
                cur->right = cur->right->left;
            }
            cur = cur->right;
        }
        return root;
    }
};

将有序数组转换为二叉搜索树

108. 将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。

高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

思路：
由于二叉搜索树的特性，每次选择mid作为分割点，然后递归左右区间即可

左闭右闭区间

class Solution {
private:
    TreeNode* traversal(vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;
        int mid = left + ((right - left) / 2);
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = traversal(nums, left, mid - 1);
        root->right = traversal(nums, mid + 1, right);
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root = traversal(nums, 0, nums.size() - 1);
        return root;
    }
};

取数组中间元素的位置，不难写出int mid = (left + right) / 2;，这么写其实有一个问题，就是数值越界，例如left和right都是最大int，这么操作就越界了，在二分法 (opens new window)中尤其需要注意！

对于无序数组构造普通二叉搜索：

数组排序后利用上述方法
采用插入法构造二叉搜索树

6057. 统计值等于子树平均值的节点数

给你一棵二叉树的根节点 root ，找出并返回满足要求的节点数，要求节点的值等于其子树中值的平均值。

注意：

n 个元素的平均值可以由 n 个元素 求和 然后再除以 n ，并 向下舍入 到最近的整数。
root 的 子树 由 root 和它的所有后代组成。

输入：root = [4,8,5,0,1,null,6]
输出：5
解释：
对值为 4 的节点：子树的平均值 (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4 。
对值为 5 的节点：子树的平均值 (5 + 6) / 2 = 11 / 2 = 5 。
对值为 0 的节点：子树的平均值 0 / 1 = 0 。
对值为 1 的节点：子树的平均值 1 / 1 = 1 。
对值为 6 的节点：子树的平均值 6 / 1 = 6 。

int ans;
pair<int,int> solve(TreeNode *u){
    int sum=u->val,siz=1;
    if(u->left){
        auto ret=solve(u->left);
        sum+=ret.first;
        siz+=ret.second;
    }
    if(u->right){
        auto ret=solve(u->right);
        sum+=ret.first;
        siz+=ret.second;
    }
    if(sum/siz==u->val)++ans;
    return {sum,siz};
}

class Solution {
public:
    int averageOfSubtree(TreeNode* root) {
        ans=0;
        solve(root);
        return ans;
    }
};

前缀树（字典树）

字典树，是一种空间换时间的数据结构，又称Trie树、前缀树，是一种树形结构(字典树是一种数据结构)，典型用于统计、排序、和保存大量字符串。所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

class Trie {
private:
    vector<Trie*> child;// 指向子节点的指针数组
    bool isEnd;//表示该节点是否为字符串的结尾
public:
    Trie():child=vector<Trie*>(26),isEnd=false{}
};

对于字典树，有三个重要性质：

根节点不包含字符，除了根节点每个节点都只包含一个字符。root节点不含字符这样做的目的是为了能够包括所有字符串。
从根节点到某一个节点，路过字符串起来就是该节点对应的字符串。
每个节点的子节点字符不同，也就是找到对应单词、字符是唯一的。

实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

class Trie {
private:
    vector<Trie*> child;
    bool isEnd = false;
public:
    Trie() : child(26, nullptr) {}

    void insert(const string& word) {
        Trie* node = this;
        for (const char c : word) {
            const int idx = c - 'a';
            if (node->child[idx] == nullptr) {
                node->child[idx] = new Trie();
            }
            node = node->child[idx];
        }
        node->isEnd = true;
    }

    bool search(const string& word) const {
        const Trie* node = searchPrefix(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(const string& prefix) const {
        return searchPrefix(prefix) != nullptr;
    }

private:
    Trie* searchPrefix(const string& prefix) const {
        Trie* node = this;
        for (const char c : prefix) {
            const int idx = c - 'a';
            if (node->child[idx] == nullptr) {
                return nullptr;
            }
            node = node->child[idx];
        }
        return node;
    }
};

https://leetcode.cn/problems/implement-trie-prefix-tree/solution/by-lfool-k6hb/

2.7 图论

图的构造

使用邻接表存储图结构简单实现

#include <vector>

using namespace std;

// 边的结构体
struct Edge {
  int to;       // 边的终点
  int weight;   // 边的权重，如果是无权图可以省略

  Edge(int _to, int _weight = 1) : to(_to), weight(_weight) {}
};

// 图的结构体
struct Graph {
  int n;                        // 图的节点数
  vector<vector<Edge>> adj;     // 邻接表

  Graph(int _n) : n(_n), adj(_n) {}

  // 添加一条从 from 到 to 权重为 weight 的边
  void add_edge(int from, int to, int weight = 1) {
    adj[from].push_back(Edge(to, weight));
  }

  // 获取节点 v 的所有邻居
  const vector<Edge>& neighbors(int v) const {
    return adj[v];
  }
};

使用邻接矩阵存储的图的实现

#include <vector>

using namespace std;

// 图的结构体
struct Graph {
  int n;                // 图的节点数
  vector<vector<int>> adj;  // 邻接矩阵

  Graph(int _n) : n(_n), adj(_n, vector<int>(_n)) {}

  // 添加一条从 from 到 to 的边
  void add_edge(int from, int to) {
    adj[from][to] = 1;
    adj[to][from] = 1;    // 如果是无向图，邻接矩阵是对称的，需要同时修改两个方向的值
  }

  // 获取节点 from 到 to 是否有边相连
  bool has_edge(int from, int to) const {
    return adj[from][to] == 1;
  }

  // 获取节点 v 的所有邻居
  vector<int> neighbors(int v) const {
    vector<int> res;
    for (int i = 0; i < n; i++) {
      if (adj[v][i] == 1) {
        res.push_back(i);
      }
    }
    return res;
  }
};

2.7.2 广度优先搜索

2.7.3 深度优先搜索

华为OD机试 - 计算快递主站点

快递业务范围有N个站点，A站点与B站点可以中转快递，则认为A-B站可达，如果A-B可达，B-C可达，则A-C可达。
现在给N个站点编号0、1、…n-1，用s[i][j]表示i-j是否可达，s[i][j]=1表示i-j可达，s[i][j]=0表示i-j不可达。
现用二维数组给定N个站点的可达关系，请计算至少选择从几个主站点出发，才能可达所有站点（覆盖所有站点业务）。
说明：s[i][j]与s[j][i]取值相同。

输入描述
第一行输入为N（1 < N < 10000），N表示站点个数。
之后N行表示站点之间的可达关系，第i行第j个数值表示编号为i和j之间是否可达。
输出描述
输出站点个数，表示至少需要多少个主站点。

这道题是一个图论问题，可以使用深度优先搜索或广度优先搜索来解决，类似于求解图的连通分量个数

#include <iostream>
#include <vector>
using namespace std;
// dfs递归函数，找到连通的所有节点
void dfs(const vector<vector<int>>& graph, vector<int>& visited, int node) {
    visited[node] = true;
    for (int i = 0; i < graph.size(); i++) {
        if (graph[node][i] && !visited[i]) {
            dfs(graph, visited, i);
        }
    }
}
int main() {
    int n;
    cin >> n;
    vector<vector<int>> graph(n, vector<int>(n));
    vector<int> visited(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(graph, visited, i);
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

将s矩阵设置为全局变量的好处是，在bfs和bfs_solve函数中都可以直接访问s矩阵，无需传递参数，提高了代码的可读性和可维护性。此外，在某些编译器中，将大的局部变量分配在栈上可能导致栈溢出问题，将其设置为全局变量可以避免这个问题。

#include <iostream>
#include <queue>
#include <vector>

using namespace std;
const int N = 10000;

int n;          // 站点个数
int s[N][N];    // 可达关系
bool visited[N];  // 记录节点是否被访问过

// BFS 搜索以 start 为起点的连通块
void bfs(int start) {
  queue<int> q;
  visited[start] = true;
  q.push(start);
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    for (int i = 0; i < n; i++) {
      if (s[cur][i] && !visited[i]) {
        visited[i] = true;
        q.push(i);
      }
    }
  }
}

// BFS 求解问题
int bfs_solve() {
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (!visited[i]) {
      bfs(i);
      ans++;
    }
  }
  return ans;
}

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> s[i][j];
    }
  }
  cout << bfs_solve() << endl;
  return 0;
}

2.8 排序

桶排序

排序思想：主要利用了函数的映射关系和桶划分两种思想来把数组中的所有元素分为若干个数据块，也就是若干个桶，然后对每个桶里的数据进行排序，最后将所有桶里的数据依次排列即可。

应用场景：桶排序适用于数据分布均匀的情况，如果数据分布不均匀的话，桶的数量会非常多，空间开销会很大

/*
 以对两位的正整数数据排序为案例 实现桶排序
*/
#include <iostream>
#include <vector>
struct KeyNode{
    int key;
    struct KeyNode *next;
};
void bucket_sort(std::vector<int>& keys, int bucket_size){
    std::vector<KeyNode*> bucket_table(bucket_size, nullptr);
    // Initialize the bucket table, set key to 0, and next to null
    for(int i=0; i < bucket_size; ++i){
        KeyNode* node = new KeyNode{0, nullptr};
        bucket_table[i] = node;
    }
    // Insert the values to the buckets
    for(int j=0; j < keys.size(); ++j){
        int index = keys[j] / 10;
        
        KeyNode *node = new KeyNode{keys[j], nullptr};
        KeyNode *p = bucket_table[index];
        // If the bucket has no values, add node to the head and increase the number of keys
        if(p->key == 0){
            bucket_table[index]->next = node;
            ++(bucket_table[index]->key);
        }else{ //If the bucket has values, find the right position to insert
            while(p->next != nullptr && p->next->key <= node->key)
                p = p->next;
            node->next = p->next;
            p->next = node;
            ++(bucket_table[index]->key);
        }
    }
    //print result
    for(int i = 0; i < bucket_size; ++i){
        for(KeyNode* k = bucket_table[i]->next; k != nullptr; k = k->next){
            std::cout << k->key << " ";
        }
    }
    std::cout<<"\n";
}
int main(){
    std::vector<int> raw = {32,21,99,67,75,42,36,71,12,90,41,79,31};
    int size = raw.size();
    bucket_sort(raw, 10);
    return 0;
}

++(bucket_table[index]->key) 的作用是将桶中的元素数量加 1，桶中的 key 字段表示该桶中元素的数量。在往桶中插入元素时，如果该桶还没有任何元素，则在该桶的头部插入一个元素，并将 key 字段设置为 1。如果该桶中已经存在元素，则在正确的位置插入元素，并将 key 字段加 1，表示桶中元素的数量增加了 1。

++(bucket_table[index]->key) 中的括号是必需的，因为 -> 的优先级比 ++ 更高，因此先执行的是 bucket_table[index]->key++，这并不是我们所期望的。因此，我们需要将 bucket_table[index]->key 放在括号中，以确保先执行 ++ 操作

#include <iostream>
#include <vector>

using namespace std;

// 桶排序
void bucketSort(vector<int>& data) {
  // 确定桶的个数
  int bucketSize = 10;

  // 创建桶
  vector<vector<int>> buckets(bucketSize);

  // 将待排序的元素分配到桶中
  for (int i = 0; i < data.size(); i++) {
    int bucketIndex = data[i] / bucketSize;
    buckets[bucketIndex].push_back(data[i]);
  }

  // 对每个桶中的元素进行排序
  for (int i = 0; i < buckets.size(); i++) {
    sort(buckets[i].begin(), buckets[i].end());
  }

  // 按照桶的顺序依次将元素输出
  for (int i = 0; i < buckets.size(); i++) {
    for (int j = 0; j < buckets[i].size(); j++) {
      cout << buckets[i][j] << " ";
    }
  }
}

int main() {
  vector<int> data = {2, 5, 1, 3, 4, 6, 7, 8, 9, 10};

  cout << "原始数据：" << endl;
  for (int i = 0; i < data.size(); i++) {
    cout << data[i] << " ";
  }
  cout << endl;

  bucketSort(data);

  cout << "排序后的数据：" << endl;
  for (int i = 0; i < data.size(); i++) {
    cout << data[i] << " ";
  }
  cout << endl;

  return 0;
}

快速排序

#include <iostream>
#include <queue>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::vector;

int disPlace(vector<int>& nums, int lf, int rt){
    int pivot = nums[lf];
    while (lf < rt) {
        while (lf < rt && nums[rt] >= pivot) --rt;
        nums[lf] = nums[rt];
        while (lf < rt && nums[lf] < pivot) ++lf;
        nums[rt] = nums[lf];
    }
    nums[lf] = pivot;
    return lf;
}

void quickSort(vector<int>& nums, int lf, int rt){
    if (lf > rt) return;
    int index = disPlace(nums, lf, rt);
    quickSort(nums, lf, index - 1);
    quickSort(nums, index + 1, rt);
}

int main() {
    vector<int> nums={2, 3, 5, 1, 9, 8, 7, 6, 0, 4};
    quickSort(nums, 0, nums.size() - 1);
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i] << " ";
    }
    return 0;
}

面试总结

int pivot(std::vector<int>& nums, int left, int right); // 普通快速排序
int pivot_stable(std::vector<int>& nums, int left, int right); // 稳定的快速排序
std::pair<int, int> pivot_three(std::vector<int>& nums, int left, int right); // 三路归并
v
    oid quickSort(std::vector<int>& nums, int left, int right)
{
    if (left >= right)
        return;
    // int piv = pivot(nums, left, right);
    // int piv = pivot_stable(nums, left, right);

    // quickSort(nums, left, piv - 1);
    // quickSort(nums, piv + 1, right);
    std::pair<int, int> piv = pivot_three(nums, left, right);
    quickSort(nums, left, piv.first - 1);
    quickSort(nums, piv.second + 1, right);
}

int pivot(std::vector<int>& nums, int left, int right)
{
    int p = nums[left];
    while (left < right) {
        while (left < right && nums[right] > p)
            --right;
        nums[left] = nums[right];
        while (left < right && nums[left] <= p)
            ++left;
        nums[right] = nums[left];
    }
    nums[left] = p;
    return left;
}
int pivot_stable(std::vector<int>& nums, int left, int right)
{
    std::vector<int> vec_p(right - left + 1, 0);
    int piv = nums[left];
    int vec_lf = 0, local = 0;
    for (int i = left + 1; i <= right; ++i) {
        if (nums[i] < piv)
            vec_p[vec_lf++] = nums[i];
    }
    local = vec_lf;
    vec_p[vec_lf++] = piv;
    for (int i = left + 1; i <= right; ++i) {
        if (nums[i] >= piv)
            vec_p[vec_lf++] = nums[i];
    }
    vec_lf = 0;
    int res = 0;
    for (int i = left; i <= right; i++) {
        if (local == vec_lf) {
            res = i;
        }
        nums[i] = vec_p[vec_lf++];
    }
    return res;
}

std::pair<int, int> pivot_three(std::vector<int>& nums, int left, int right)
{
    int piv = nums[left];
    int cur = left + 1;
    while (cur <= right) {
        if (nums[cur] < piv) {
            std::swap(nums[cur++], nums[left++]); // cur++
        } else if (nums[cur] > piv) {
            std::swap(nums[cur], nums[right--]); // cur right--
        } else {
            cur++;
        }
    }
    return { left, right };
}

第2章 数据结构基础

2.1 数组

基础

二分查找的实现

二分法查找边界问题

双指针

求中位数

2.2 链表

理论基础

移除链表元素

翻转链表

链表相交节点问题 链表相交

链表环入口问题 环形链表

2.3 哈希表

理论基础

常见的三种哈希结构

常见案例

2.4 字符串

理论基础

字符串与数值的转化

KMP算法

2.5 栈与队列

容器以及容器适配器

vector

stack

deque

queue队列

priority_queue优先队列

C/C++排序函数中cmp()比较函数的写法

操作基本和队列相同

定义:

实例

堆的实现

手撕堆排序

利用deque构造单调队列

单调栈

2.6 树

树的生成

二叉树的性质

二叉树的遍历

广度优先搜索（层次遍历）

深度优先搜索

翻转二叉树

对称二叉树

相同二叉树以及另一棵树的子树

二叉树的最小深度

完全二叉的节点个数

平衡二叉树

二叉树的所有路径

递归函数中自定义参数和全局变量，参数与参数引用区别

二叉树左叶子节点之和

找树左下角节点值

路径总和

从中序与后序遍历序列构造二叉树

合并二叉树

二叉搜索树

验证二叉搜索树

二叉搜索树中的众数

二叉树的最近公共祖先

二叉搜索树的最近公共祖先

二叉搜索树节点的插入

删除二叉搜索树中的节点

修剪二叉搜索树

将有序数组转换为二叉搜索树

前缀树（字典树）

2.7 图论

图的构造

华为OD机试 - 计算快递主站点

2.8 排序

桶排序

快速排序

第2章数据结构基础

链表相交节点问题链表相交

链表环入口问题环形链表