方法一：递归二叉树的后序遍历顺序：左节点->右节点->根节点。先依次进入左右子树进行递归，再保留根节点的值。时间复杂度：o(n)。需要遍历二叉树的所有节点，需要o(n)。空间复杂度：o(n)。需要开辟空间保存中序遍历的节点值。 class Solution { public: void post_search(TreeNode* root, vector<int>& post_tree) { //节点为空时返回 if(root == nullptr) return; //递归遍历左子树 post_search(root->left, post_tree);...

方法一：递归二叉树的中序遍历顺序：左节点->根节点->右节点。先递归遍历左子树，再保存根节点的值，再递归遍历右子树。时间复杂度：o(n)。需要遍历二叉树的所有节点，需要o(n)。空间复杂度：o(n)。需要开辟空间保存中序遍历的节点值。 class Solution { public: void in_search(TreeNode* root, vector<int>& in_tree) { //节点为空时返回 if (root == nullptr) return; //中序遍历先遍历左节点 in_search(root->left, in_tree);...

方法一：递归二叉树的前序遍历顺序：根节点->左节点->右节点。先保存根节点的值，依次进入左右子树进行递归。时间复杂度：o(n)。需要遍历二叉树的所有节点，需要o(n)。空间复杂度：o(n)。需要开辟空间保存前序遍历的节点值。 class Solution { public: void pre_search(TreeNode* root, vector<int>& pre_tree) { //当节点为空时返回 if (root == nullptr) return; //保存根节点的值 pre_tree.push_back(root->val); //遍历左...

方法：双指针使用两个指针分别指向两个数组的头元素，分别得到两个点号之间的数字，通过比较两个数字的大小即可得到两个版本号的大小。时间复杂度：o(n)空间复杂度：o(1) class Solution { public: int compare(string version1, string version2) { int i = 0; int j = 0; while (i < version1.size() || j < version2.size()) { int num1 = 0; int num2 = 0; //每次截取version1、version2两个点号之间的数字比较...

方法：归并排序题目中要求得出一个数组的所有逆序对（前面的数大于后面的数组成一个逆序对），归并排序将数组向下拆分至单个元素的数组，然后向上递归，不断地合并两个数组，直到将整个数组完成排序。如果是两个有序的数组，我们就可以很容易得到该元素逆序对的数目，而不用一个个进行遍历比较。时间复杂度：o(nlogn)。递归的深度有logn层，每层需要遍历n个元素进行排序归并，所以时间复杂度为o(nlogn)。空间复杂度：o(n)。数组需要一个o(n)的空间来保存排序后的数组，每层都需要o(n)，一层排序合并完后可以释放掉该空间，所以虽然递归有logn层，但是只需要o(n)的空间。 class Solution...

方法：二分法首先根据题目的条件2和条件3，可以得出一个结论：数组一定能找到峰值。因为数组相邻的元素不会相等，所以相邻的元素一定是有递增或者递减的趋势。如果数组是一个递增数组和递减数组，根据条件2也可以得到：递增数组的峰值是最后一个元素；递减数组的峰值是第一个元素。步骤：1、找到数组的中间元素mid；2、判断mid与mid+1的大小关系。 如果mid+1大于mid时，右侧一定能找到峰值。因为右边是向上的会对应两种情况：1、右侧会在某个元素开始下降；2、右侧一直向上递增。第一种情况：如果右侧会在某个数组元素开始下降，那么这个数组元素就是峰值；第二种情况，如果右侧一直向上递增，这时候可能有人就会觉得...

方法：线性搜索通过观察二维数组可以发现，左下角的元素是所在列最大的值，是所在行最小的值；右上角的元素是所在列最小的值，是所在行最大的值。如果从左下角或者右上角进行搜索，则一次搜索可以排除一行或者一列的元素。下列以右上角进行搜索：时间复杂度：0(n+m)空间复杂度：o(1) class Solution { public: bool Find(int target, vector<vector<int> >& array) { int col = array.size(); int row = array[0].size(); //特殊情况处理 if (col == 0 ...

方法：二分法题设中的条件：非降序的数组进行旋转。非降序说明数组是升序数组且可能有重复元素。通过观察可以得到：对于一个非降序的数组，取数组的中间元素与数组最右边的元素进行比较，如果中间元素大于最右边元素，最小值一定在中点右侧（不包括中点）；如果中间元素小于最右边元素，最小值一定在中点左侧（包括中点）；如果中间元素等于最右边元素，这时无法判断在哪一侧，但是可以将最右侧元素筛除掉。时间复杂度：o(logn)空间复杂度：o(1) class Solution { public: int minNumberInRotateArray(vector<int>& nums) { //特殊情况处理...

方法：二分法题设是一个升序且无重复元素的数组，利用二分法能很容易的查找元素。1、获取数组的中间元素，会有三种情况： 如果目标值等于中间元素即找到； 如果目标值小于中间元素，则目标值在左侧； 如果目标值大于中间元素，则目标值在右侧；2、不断的缩小范围，直到最终只剩一个元素，若仍然没找到目标值则返回-1；否则返回下标。时间复杂度：o(logn)空间复杂度：o(1) class Solution { public: int search(vector<int>& nums, int target) { if (nums.size() == 0) return -1; int left =...

快排参考博客：链接1、问题分析 快排的中心思想：分而治纸。通过选取基准值将要排序的数据分割成独立的两部分，其中一部分的所有数据都比基准值小，另一部分的所有数据都比基准值大，然后再按此方法对这两部分数据进行快速排序，整个排序过程可以递归进行，以此使所有数据变成有序序列。2、算法设计1、分解 先从数列中取出一个元素作为基准元素。一基准元素为标准，将问题分解为两个子序列，使小于或者等于基准元素的子序列在左侧，使大于基准元素的子序列在右侧。2、治理 对两个子序列进行快速排序（递归快速排序）。3、合并 将排好的两个子序列合并在一起，得到原问题的解。其中基准元素的选取可以有以下形式： ①：取第一个元素。(...

方法一：归并排序利用双指针和分治（递归）的思想来求解可以将问题分解为两个有序链表的合并的小问题，并且不断地向上递归，最终就可以将K个链表按顺序合并到一起。时间复杂度：o(nlogk)；递归有logk层，n为所有链表的总结点数，复杂度为o(nlogk)。空间复杂度：o(logk)，需要logk的递归栈。 class Solution { public: //合并两个有序链表 ListNode* merge(ListNode* phead1, ListNode* phead2) { if (phead1 == nullptr) return phead2; if (phead2 == nullpt...

方法一：双指针求解1、设置一个指针cur指向表头（为了解决表头就是重复元素的情况）；2、若cur->next与cur->next->next是重复元素，将cur->next向后移动直到指向不等于该元素的结点。时间复杂度：o(n)空间复杂度：o(1) class Solution { public: ListNode* deleteDuplicates(ListNode* head) { //特殊情况处理 if (head == nullptr || head->next == nullptr) return head; //设置表头 ListNode* res =...

方法一：双指针1、设置两个指针，奇数指针和偶数指针；2、将奇数指针的下一结点为偶数指针的下一个结点；奇数指针移动到下一个结点后，此时将偶数指针的下一个结点设置为奇数指针的下一个结点，移动偶数指针。时间复杂度：o(n)空间复杂度：o(1)，不需要辅助空间 class Solution { public: ListNode* oddEvenList(ListNode* head) { //特殊情况处理 if (head == nullptr || head->next == nullptr) return head; ListNode* odd = head; ListNode* even ...

方法一：归并排序1、利用归并排序将链表分而治之，不断地将链表从中间结点拆解为两个链表；2、拆解至单个结点后进行排序，将问题转化为两个排序好的链表融合为一个链表的问题；自下而上递归将两个链表进行融合，最终得到排序后的链表。利用快慢指针得到链表的中间结点时间复杂度：o(nlog2​n)，每级划分最坏需要遍历链表全部元素，因此为o(n)，每级合并都是将同级的子问题链表遍历合并，因此也为o(n)，分治划分为二叉树型，一共有o(log2​n)层，因此复杂度为o((n+n)∗log2​n)=o(nlog2​n)。空间复杂度：o(log2​n)，递归栈的深度最坏为树型递归的深度，log2​n层。 class...