中序遍历 首先设置一个全局变量pre，保存中序遍历前一个结点，在中序遍历的过程中完善指针指向即可。 C++代码： class Solution { public: TreeNode *pre; TreeNode* Convert(TreeNode* pRootOfTree) { if (!pRootOfTree) return pRootOfTree; TreeNode *p = pRootOfTree; while (p->left) {p = p->left;} inorder(pRootOfTre...

队列 不同于普通的层序遍历，每次循环要获取该层的长度，即把队列出光 C++代码： class Solution { public: vector<vector<int> > levelOrder(TreeNode* root) { vector<vector<int>> ans; if (!root) return ans; queue<TreeNode *> qu; qu.push(root); while (!qu.empty()) { ...

C++代码： class Solution { private: vector<int> ans; public: vector<int> postorderTraversal(TreeNode* root) { backTrack(root); return ans; } void backTrack(TreeNode *root) { if (root) { backTrack(root->left); backTrack(root-...

C++代码： class Solution { private: vector<int> ans; public: vector<int> inorderTraversal(TreeNode* root) { midTrack(root); return ans; } void midTrack(TreeNode *root) { if (root) { midTrack(root->left); ans.push_back(root-&...

C++代码： class Solution { private: vector<int> ans; public: vector<int> preorderTraversal(TreeNode* root) { preTrack(root); return ans; } void preTrack(TreeNode *root) { if (root) { ans.push_back(root->val); preTrack(root-&...

二分 二分时每次与右端点进行判断，注意相等的时候，右端点减一处理。 此外不能与左端点击进行比较。 情况1 ：1 2 3 4 5 ， arr[mid] = 3. target = 1, arr[mid] > target, 答案在mid 的左侧。 情况2 ：3 4 5 1 2 ， arr[mid] = 5, target = 3, arr[mid] > target, 答案却在mid 的右侧。 所以不能把左端点当做target。 class Solution { public: int minNumberInRotateArray(vector<int> rota...

字符串 简单字符串处理 C++代码： class Solution { public: int compare(string version1, string version2) { int i = 0, j = 0, len1 = version1.size(), len2 = version2.size(); while (true) { long long pa = 0, pb = 0; while (i < len1) { if (version1[i] == ...

归并排序 归并排序进行merge时，左右两个区间均是有序的，当选择右边区间元素时，左边区间的每个元素都比当前选择元素大，即有mid - i + 1个逆序对。所以我们可以在归并排序的过程中顺便求出逆序对。 C++代码： class Solution { private: int cnt; vector<int> a, b; public: int InversePairs(vector<int> data) { a = b = data; cnt = 0; mergeSort(0, a.size() ...

二分 二分查找的灵活运用，nums[mid]和nums[mid+1]进行比较。若nums[mid] < nums[mid+1]，说明在上升，l = mid + 1；若nums[mid] > nums[mid+1]，说明在下降，r = mid。 C++代码： class Solution { public: int findPeakElement(vector<int>& nums) { int l = 0, r = nums.size() - 1; while (l < r) { int mi...

二分法 二分的灵活运用，二分的话，就是经过每次二分，可以确定下次该在哪一部分查找，从而舍去一部分查找区间，节省时间。本题考虑到二维数组是有序的，我们要选择一个位置，当和target比较好后，可以确定下一个位置。这里可以选择右上角或左下角的位置，以右上角为例，设右上角元素array[i][j]值为val，若val = target，返回true；若val > tar，因为val所在列的元素都比val大，所以j--；若val < tar，因为val所在行的元素都比val小，所以i++，左下角同理。 C++代码： class Solution { public: bool Fin...

简单二分 C++代码： class Solution { public: int search(vector<int>& nums, int target) { if (nums.empty()) return -1; int l = 0, r = nums.size() - 1; while (l <= r) { int mid = (l + r) / 2; if (nums[mid] == target) { return mid...

双指针 因为链表是升序的，我们可以利用这一特性，用一个指针p遍历相同的元素，直到这个指针指向的元素和下一个不相等，这时我们就可以改变指针pre->next的指向，达到删除重复元素的目的。指针pre始终指向不重复的元素。初始化时，pre初始化指向前置结点。 C++代码： class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if (!head || !head->next) {return head;} ListNode *vhead = new ListNo...

双指针 用双指针遍历链表，有重复的直接进行删除操作，注意初始化 C++代码： class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if (!head || !head->next) {return head;} ListNode *pre = head, *p = head->next; while (p) { if (pre->val == p->val) { pre-&...

模拟 借助两个vector模拟即可 C++代码： class Solution { public: ListNode* oddEvenList(ListNode* head) { if (!head) {return NULL;} if (head->next == NULL) { return head; } vector<ListNode *> a, b; for (int i = 0; head; i++, head = head->next) { ...