打卡记录

235. 二叉搜索树的最近公共祖先 链接：235. 二叉搜索树的最近公共祖先 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 利用二叉搜索树的性质，可以用数值大小确定子树，第一次遇到的在 [p, q] 或者 [q, p] 间的数，就是最近公共祖先； BST 中，对于当前节点 cur，有三种情况： 情况一：cur 的值比 p 和 q 都大。说明 p 和 q 都在 cur 的左子树里，公共祖先一定在左边，cur 不是答案。 情况二：cur 的值比 p 和 q 都小。同理，都在右子树，往右走。 情况三：cur 的值在 p 和 q 之间（含等于）。这时候只有两种可能： p 和 q 分别在 cur 的左右子树 → cur 就是公共祖先 cur 本身就是 p 或 q 中的一个，另一个在它的子树里 → cur 也是公共祖先 看完题解后的想法 – 实现中遇到的困难 需要确定 p 和 q 的大小关系； 代码 class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (p->val > q->val) swap(p, q); TreeNode* cur = root; while (cur) { if (cur->val >= p->val && cur->val <= q->val) { return cur; } else if (cur->val < p->val) { cur = cur->right; } else { cur = cur->left; } } return nullptr; } }; 701. 二叉搜索树中的插入操作 链接：701. 二叉搜索树中的插入操作 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 二叉搜索树，可以直接比大小前进；然后找到空位就可以插进去了； ...

530. 二叉搜索树的最小绝对差 链接：530. 二叉搜索树的最小绝对差 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 中序遍历是有序的，直接用当前减过去； 看完题解后的想法 – 实现中遇到的困难 需要对最左节点进行一个特判，因为最左节点没有可以相减的； 代码 class Solution { public: int res = INT_MAX; int prev = -1; // -1 表示还没访问过任何节点 void dfs(TreeNode* root) { if (!root) return; dfs(root->left); if (prev != -1) { res = min(res, root->val - prev); // BST中序是升序，不需要abs } prev = root->val; dfs(root->right); } int getMinimumDifference(TreeNode* root) { dfs(root); return res; } }; 501. 二叉搜索树中的众数 链接：501. 二叉搜索树中的众数 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 遍历+哈希，直接在递归中怎么做不知道； ...

654. 最大二叉树 链接：654. 最大二叉树 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 和LC105, 106一样, 但是逻辑更加简单,直接采用传index; 看完题解后的想法 – 实现中遇到的困难 注意index是全局index所以直接传 代码 class Solution { public: TreeNode* recurse(vector<int>& nums, int begin, int end) { if (begin == end) return nullptr; // 1. 找到max值和index，这就是root int indexRoot = begin; for (int i = begin; i < end; i++) { if (nums[i] > nums[indexRoot]) { indexRoot = i; } } TreeNode* root = new TreeNode(nums[indexRoot]); // 2. 挂树+直接传index做分组，注意index是全局index所以直接传 root->left = recurse(nums, begin, indexRoot); root->right = recurse(nums, indexRoot+1, end); return root; } TreeNode* constructMaximumBinaryTree(vector<int>& nums) { return recurse(nums, 0, (int)nums.size()); } }; 617. 合并二叉树 链接：617. 合并二叉树 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 使用递归， 返回 root1 ， 只要 root1 没有某棵树， 就挂上 root2 的； ...

513. 找树左下角的值 链接：513. 找树左下角的值 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 层序遍历，每层的第一个值 看完题解后的想法 实现中遇到的困难 代码 class Solution { public: int findBottomLeftValue(TreeNode* root) { int res; if (!root) { return res; } queue<TreeNode*> q; q.push(root); while (!q.empty()) { int num = q.size(); for (int i = 0; i < num; i++) { TreeNode* cur = q.front(); q.pop(); if (i == 0) { res = cur->val; } if (cur->left) { q.push(cur->left); } if (cur->right) { q.push(cur->right); } } } return res; } }; 112. 路径总和 链接：112. 路径总和 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 DFS+回溯；栈自带回溯； ...

110. 平衡二叉树 链接：110. 平衡二叉树 文章：代码随想录 视频：B站讲解 状态：❌ 第一想法 没想出来; 看完题解后的想法 从底到顶递归算高度,很巧妙; 对于底层叶子往上递归的过程需要理解; 实现中遇到的困难 代码 class Solution { public: bool isBalanced(TreeNode* root) { return getHigh(root) != -1; } int getHigh(TreeNode* root) { // 1. 递归到底之后返回 0 if (!root) { return 0; } // 2. 左子树高度 int left = getHigh(root->left); if (left == -1) return -1; // 3. 右子树高度 int right = getHigh(root->right); if (right == -1) return -1; if (abs(left - right) > 1) { return -1; } // 4. 返回当前高度,注意因为叶子节点的左右子树都是 nullptr 返回了 0,高度为 1 return 1 + max(left, right); } }; 257. 二叉树的所有路径 链接：257. 二叉树的所有路径 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 使用递归，一层加一个路径； ...

226. 翻转二叉树 链接：226. 翻转二叉树 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 遍历节点，然后交换节点的左右子树，DFS和BFS都能做； 看完题解后的想法 注意中序遍历因为是 左-根-右 ，在根节点交换完之后要继续访问左子树，因为已经交换了； 实现中遇到的困难 中序和后序的迭代写法还是记不牢； 代码 前序递归解： class Solution { public: TreeNode* invertTree(TreeNode* root) { dfs(root); return root; } void dfs(TreeNode* root) { if (!root) return; TreeNode* tmp = root->right; root->right = root->left; root->left = tmp; dfs(root->left); dfs(root->right); } }; 中序递归解： class Solution { public: TreeNode* invertTree(TreeNode* root) { dfs(root); return root; } void dfs(TreeNode* root) { if (!root) return; dfs(root->left); TreeNode* tmp = root->right; root->right = root->left; root->left = tmp; dfs(root->left); // 交换左右所以记得继续走左 } }; 前序迭代： ...

需要了解二叉树的种类，存储方式，遍历方式以及二叉树的定义。 文章：代码随想录 - 二叉树理论基础 DFS 144. 二叉树的前序遍历 链接：144. 二叉树的前序遍历 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 根 - 左 - 右 可以递归dfs，还可以迭代用栈模拟，还可以用Morris，但是Morris太复杂了； 看完题解后的想法 前序是"根-左-右"，弹出就访问，访问完把左右子节点压栈。节点被弹出只有一种含义：该访问了。不存在"我还要回来"的情况。 实现中遇到的困难 注意压栈的顺序是后访问的先压; 代码 递归解：(爆栈风险) class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> res; dfs(root, res); return res; } void dfs(TreeNode* root, vector<int>& res) { if (root == nullptr) { return ; } res.push_back(root->val); dfs(root->left, res); dfs(root->right, res); } }; 迭代解：(面试要求) class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> res; if (!root) { return res; } stack<TreeNode*> st; st.push(root); while (!st.empty()) { TreeNode* cur = st.top(); st.pop(); res.push_back(cur->val); // 先压后访问的 if (cur->right) { st.push(cur->right); } // 再压先访问的 if (cur->left) { st.push(cur->left); } } return res; } }; 145. 二叉树的后序遍历 链接：145. 二叉树的后序遍历 文章：代码随想录 视频：B站讲解 状态：❌ 第一想法 左 - 右 - 根, 迭代解不会; ...

150. 逆波兰表达式求值 链接：150. 逆波兰表达式求值 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 逆波兰表达式 逆波兰表达式： 逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。 逆波兰表达式主要有以下两个优点： 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中 看完题解后的想法 —— 实现中遇到的困难 注意第一次出栈的是右操作数，第二次出栈的是左操作数； 代码 class Solution { public: int evalRPN(vector<string>& tokens) { stack<int> st; for (string& t : tokens) { if (t == "+" || t == "-" || t == "*" || t == "/") { int a = st.top(); st.pop(); int b = st.top(); st.pop(); if (t == "+") { st.push(b + a); } else if (t == "-") { st.push(b - a); } else if (t == "*") { st.push(b * a); } else { st.push(b / a); } } else { st.push(stoll(t)); } } return st.top(); } }; 239. 滑动窗口最大值 链接：239. 滑动窗口最大值 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 老员工比新员工菜就优化，老员工大于35也优化 ...

232. 用栈实现队列 链接：232. 用栈实现队列 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 一个栈 s1 用来入队，一个栈 s2 用来出队； 看完题解后的想法 最开始每次把数据从 s1 倒入 s2 还要把 s2 中的数据倒回去，为了保持顺序一致； 但是其实可以做一个简化，只有s2中空了才从s1中补充，这样其实是分段连续的； 实现中遇到的困难 —— 代码 class MyQueue { public: MyQueue() { } void push(int x) { s1.push(x); } int pop() { transfer(); int res = s2.top(); s2.pop(); return res; } int peek() { transfer(); int res = s2.top(); return res; } bool empty() { return s1.empty() && s2.empty(); } private: stack<int> s1; stack<int> s2; void transfer() { if (s2.empty()) { while (!s1.empty()) { s2.push(s1.top()); s1.pop(); } } } }; 225. 用队列实现栈 链接：225. 用队列实现栈 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 刚开始用两个queue互相捣腾数据； ...

151. 翻转字符串里的单词 链接：151. 翻转字符串里的单词 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 第一想法感觉这道题好麻烦，然后拆解任务一共三步： 去掉两端以及中见多余的空格 翻转整个字符串 挨着翻转每个单词 其中在挨着翻转每个单词的时候因为尾端没有空格，所以临时加上一个空格在翻转完之后再去掉，避免了尾处理； 看完题解后的想法 原地去空格使用双指针法， 最后需要resize，注意使用的size就是slow最后停留的index； 实现中遇到的困难 —— 代码 class Solution { public: string reverseWords(string s) { endSpace(s); reverse(s, 0, (int)s.size()-1); int left = 0; int right = 0; while (right <= (int)s.size()) { if (right == (int)s.size() || s[right] == ' ') { reverse(s, left, right-1); left = ++right; } else { right++; } } return s; } // 去掉两端以及中见多余的空格 void endSpace(string& s) { int slow = 0; for (int fast = 0; fast < (int)s.size(); fast++) { if (s[fast] != ' ') { if (slow > 0) { s[slow++] = ' '; } while (fast < (int)s.size() && s[fast] != ' ') { s[slow++] = s[fast++]; } } } s.resize(slow); } // 翻转函数 void reverse(string& s, int left, int right) { int l = left; int r = right; while (l < r) { char tmp = s[r]; s[r] = s[l]; s[l] = tmp; l++; r--; } } }; KamaCoder 55. 右旋字符串 链接：KamaCoder 55. 右旋字符串 文章：代码随想录 视频：无 状态：⚠️ 第一想法 刚开始是准备整体移动+栈来构造新的字符串； ...