AcWing 35. 反转链表（需要把解法一也写了）
解法
这里解法有两种，一种是每次从链表中摘除头结点，并放到新链表的末尾。
第二种是从头到尾一次扫描链表，扫描的同时，把指针反转。
代码(第二种解法)
迭代版本
class Solution {public:ListNode* reverseList(ListNode* head) {if (!head || !head->next) {return head;}ListNode* pre = head;ListNode* cur = head->next;while(cur) {ListNode* tmp = cur->next;cur->next = pre;pre = cur;cur = tmp;}head->next = NULL;return pre;}};
递归版本
class Solution {public:ListNode* reverseList(ListNode* head) {if (!head || !head->next) {return head;}ListNode* new_head = reverseList(head->next);head->next->next = head;head->next = NULL;return new_head;}};
AcWing 36. 合并两个排序的链表
解法
代码
class Solution { public: ListNode* merge(ListNode* l1, ListNode* l2) { ListNode * dummy = new ListNode(-1); ListNode * cur = dummy; while (l1 && l2) { if (l1->val < l2->val) { cur->next = l1; l1 = l1->next; cur = cur->next; } else { cur->next = l2; l2 = l2->next; cur = cur->next; } } while(l1) { cur->next = l1; l1 = l1->next; cur = cur->next; } while(l2) { cur->next = l2; l2 = l2->next; cur = cur->next; } return dummy->next; } };AcWing 37. 树的子结构
解法
遍历树的每一个子节点，判断是否为子树的根节点，如果匹配，则返回true
代码
class Solution { public: bool getSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { if (!pRoot1) return false; if (pRoot1->val != pRoot2->val) return false; if (pRoot2->left) { if (!getSubtree(pRoot1->left, pRoot2->left)) { return false; } } if (pRoot2->right) { if (!getSubtree(pRoot1->right, pRoot2->right)) { return false; } } return true; } bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { if (!pRoot2 || !pRoot1) return false; if (getSubtree(pRoot1, pRoot2)) return true; return hasSubtree(pRoot1->left, pRoot2) || hasSubtree(pRoot1->right, pRoot2); } };AcWing 38. 二叉树的镜像
解法
代码
class Solution { public: void mirror(TreeNode* root) { if (!root) return; swap(root->left, root->right); mirror(root->left); mirror(root->right); } };AcWing 39. 对称的二叉树
解法
其实是要判断两棵子树是否互为镜像，那就要知道互为镜像有什么特点。
互为镜像的两棵树，根节点相同，左右子树的值互为镜像。
从另一种角度理解，这棵树按照如下两种顺序遍历，结果应该完全一样：1. 左子树、根节点、右子树；2. 右子树、根节点、左子树。代码
class Solution { public: bool isMirror(TreeNode* root1, TreeNode* root2) { if (!root1 || !root2) { if (!root1 && !root2) { return true; } return false; } if (root1->val != root2->val) { return false; } return isMirror(root1->right, root2->left) && isMirror(root1->left, root2->right); } bool isSymmetric(TreeNode* root) { if (!root) return true; return isMirror(root->left, root->right); } };AcWing 40. 顺时针打印矩阵
解法
代码
class Solution { public: vector<int> printMatrix(vector<vector<int>> matrix) { if (matrix.empty() || matrix[0].empty()) { return {}; } int n = matrix.size(), m = matrix[0].size(); vector<vector<bool>> st(n, vector<bool>(m, false)); int x = 0, y = 0; int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0}; int dir = 0; vector<int> ans; for (int i = 0; i < n * m; i ++) { ans.push_back(matrix[x][y]); st[x][y] = true; int a = x + dx[dir]; int b = y + dy[dir]; if (a < 0 || a >= n || b < 0 || b >= m|| st[a][b]) { dir = (dir + 1) % 4; a = x + dx[dir]; b = y + dy[dir]; } x = a; y = b; } return ans; } };AcWing 41. 包含min函数的栈
解法
直觉上来说，包含min函数的栈，就是把栈和堆组合起来。但是这样的话，插入数字、弹出数字的复杂度均为O(logn)，查询min是O(1)，我们希望实现插入、弹出、查询min均为O(1)的做法。
这里我们需要把堆的功能，用栈实现出来。根据栈的定义来看，如果一个比它小的数先压栈，那么它出入栈并不会影响栈中的最小值。因此，我们栈里面存的元素值，一定是单调递减的，因此辅助栈是一个单调栈。代码
class MinStack { public: stack<int> stk; stack<int> min_stk; MinStack() { } void push(int x) { stk.push(x); // 如果插入的数字比单调栈的top还要小，说明会影响栈中的最小值 // 并且有可能会有重复元素，因此判断时，要带上== if (min_stk.empty() || min_stk.top() >= x) { min_stk.push(x); } } void pop() { if (stk.top() == min_stk.top()) { min_stk.pop(); } stk.pop(); } int top() { return stk.top(); } int getMin() { return min_stk.top(); } };AcWing 42. 栈的压入、弹出序列
解法
模拟题。通过模拟栈压入、弹出的顺序，看操作完成之后是否能得到空栈。
代码
class Solution { public: bool isPopOrder(vector<int> pushV,vector<int> popV) { if (pushV.size() != popV.size()) { return false; } int n = pushV.size(); stack<int> stk; for (int i = 0, j = 0; i < n; i ++) { if (stk.empty() || stk.top() != popV[j]) { stk.push(pushV[i]); } while(stk.size() && stk.top() == popV[j]) { stk.pop(); j ++; } } return stk.empty(); } };树的层次遍历
相关题目
AcWing 43. 不分行从上往下打印二叉树
AcWing 44. 分行从上往下打印二叉树
AcWing 45. 之字形打印二叉树解法
其实就是典型的层次遍历。43题直接遍历即可，44题需要判断每一层之间的区分，45题需要通过判断层数，reverse一遍对应的遍历数据。
需要给出不reverse的解法。代码
AcWing 43. 不分行从上往下打印二叉树
class Solution { public: vector<int> printFromTopToBottom(TreeNode* root) { if (!root) { return {}; } queue<TreeNode*> q; vector<int> ans; q.push(root); while(q.size()) { int cnt = q.size(); TreeNode *t = q.front(); ans.push_back(t->val); q.pop(); if (t->left) { q.push(t->left); } if (t->right) { q.push(t->right); } } return ans; } };AcWing 44. 分行从上往下打印二叉树
class Solution { public: vector<vector<int>> printFromTopToBottom(TreeNode* root) { vector<vector<int>> ans; if (!root) { return ans; } queue<TreeNode *> q; q.push(root); while(q.size()) { int cnt = q.size(); ans.push_back({}); int idx = ans.size() - 1; for (int i = 0; i < cnt; i ++) { TreeNode * t = q.front(); q.pop(); ans[idx].push_back(t->val); if (t->left) { q.push(t->left); } if (t->right) { q.push(t->right); } } } return ans; } };AcWing 45. 之字形打印二叉树
class Solution { public: vector<vector<int>> printFromTopToBottom(TreeNode* root) { vector<vector<int>> ans; if (!root) { return ans; } queue<TreeNode*> q; q.push(root); int layer = -1; while(q.size()) { layer ++; int cnt = q.size(); ans.push_back({}); int idx = ans.size() - 1; for (int i = 0; i < cnt; i ++) { auto t = q.front(); q.pop(); ans[idx].push_back(t->val); if (t->left) { q.push(t->left); } if (t->right) { q.push(t->right); } } if (layer % 2 == 1){ reverse(ans[idx].begin(), ans[idx].end()); } } return ans; } };
若有收获，就点个赞吧
0 人点赞
