代码随想录 打卡day23，24，25

2024-05-13 13:28
文章标签 随想录 代码 25 打卡 24 day23

本文主要是介绍代码随想录 打卡day23，24，25，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 二叉搜索树的最小绝对差

在这里插入图片描述
注意审题，题目当值说到是一个二叉搜索树，因此我们只需进行中序遍历即可，然后得到一个有序数组之后进行编辑，统计出来最小差。

class solution{
private:vector<int> vec;void traversal(TreeNode* root){if(root == NULL) return;traversal(root->left);vec.push_back(root->val);traversal(root->right);}
public:int getMinDif(TreeNode* root){vec.clear();traversal(root);if(vec.size()<2)return 0;int result = INT_MAX;for(int i = 1;i < vec.size(); i++){result = min(result, vec[i]-vec[i-1]);}return result;}
}

其实可以在遍历过程中进行计算和记录

class solution(
private:
int result = INT_MAX;
TreeNode* pre = NULL;
void traversal(TreeNode* cur){if(cur == NULL)return;traversal(cur->left);if(pre!=NULL){result = mim(result, cur->val - pre->val);}pre = cur;traversal(cur->right);
}
public:int getMinDif(TreeNode* root){traversal(root);return result;}
)

迭代法肯定也可以做，直接用中序遍历进行迭代：

int getMinDif(TreeNode* root){stack<TreeNode*> st;TreeNode* cur;TreeNode* pre = NULL;int result = INT_MAX;while(cur != NULL || !st.empty()){if(cur != NULL){st.push(cur);cur = cur->left;} else{cur = st.top();st.pop();if(pre != NULL){result = min(result, cur->val - pre->val);}pre = cur;cur = cur->right;}}return result;
}

2 二叉搜索树中的众数

在这里插入图片描述
如果不是二叉搜索树，那么可以简单对树进行遍历，使用map统计频率，将频率进行排序，最后取前面高频元素的集合。要把map转化数组即vector，再进行排序，当然vector里面放的也是pair<int, int>类型的数据，第一个int为元素，第二个int为出现频率。因为map不可进行直接排序

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;}
};

如果是二叉搜索树，那么根据有序性，可以进行中序遍历，两两相邻元素进行比较。弄一个指针指向前一个节点，这样每次cur（当前节点）才能和pre（前一个节点）作比较。而且初始化的时候pre = NULL，这样当pre为NULL时候，我们就知道这是比较的第一个元素。

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

如果 频率count 等于 maxCount（最大频率），当然要把这个元素加入到结果集中（以下代码为result数组），代码如下：

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

频率count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集（以下代码为result数组），因为结果集之前的元素都失效了。

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

核心代码，以上的操作放在中序遍历当中

class Solution {
private:int maxCount = 0; // 最大频率int count = 0; // 统计频率TreeNode* pre = NULL;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;pre = NULL; // 记录前一个节点result.clear();searchBST(root);return result;}
};

3 二叉树的最近公共祖先

在这里插入图片描述
这里使用回溯进行二叉树自底向上的查找过程，其实所学习的后序遍历就是一种最为常见的自底向上的过程，按照左右中的顺序进行查找。
如何去判断q和p的公共祖先呢？如果找到一个节点，发现左子树出现结点p，右子树出现结点q，或者出现相反的情况，则就说明该节点就是p和q的最近公共祖先。
在这里插入图片描述
第二种情况就是p是q的祖先，那么祖先就是结点本身。
在这里插入图片描述
采用递归三部曲进行解题：
（1）确定递归函数返回值以及参数
需要返回的是公共的祖先结点，因此输入根节点、q、p两个结点。

TreeNode* LowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)

（2）确认终止条件
如果遇到了空，就返回。还有就是当root直接和q或者p相等，说明已经找了p或者q，则直接将其返回if (root == q || root == p || root == NULL) return root;
（3）确认单层递归逻辑
实际上逻辑很简单，我们只需要判断遍历到q或者p之后，将这个root向上去返回就可以了。在这个问题中肯定是需要对整棵树进行搜索，因此代码逻辑为：

left = 递归函数(root->left);  // 左
right = 递归函数(root->right); // 右
left与right的逻辑处理;         // 中

现在我们需要考虑一下几种情况：
（1）如果这个root结点的左右子树均返回找到p/q的结果，也就是left和right都不为空，说明root就是最近公共结点。
（2）left为空，right不为空：说明目标节点就是通过right返回的，反之亦然。
在这里插入图片描述
图中节点10的左子树返回null，右子树返回目标值7，那么此时节点10的处理逻辑就是把右子树的返回值（最近公共祖先7）返回上去！
（3）左右均为空，说明没找到q和p，因此返回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) return right;return left;}
};

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

在这里插入图片描述
因为这是一个有序树，那么如果中间的结点是p和q的共同祖先，那么中间节点一定是在[p,q]区间的。因此只需要从上到下进行遍历，寻找在p，q之间的cur结点。那么第一次遇到的cur一定就是最近的公共祖先了，因为再向下搜索的时候会导致一方错过自己的祖先节点。

递归法解决问题：
（1）TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q)
（2）if(cur == NULL) return cur;
（3）单层递归逻辑：
如果是发现cur在左子树上，右子树则相反

if(cur->val > p -> val && cur-> val > q->val){TreeNode* left = traversal(cur->left,p,q);if(left!=NULL) return left;
}

整体递归代码如下：

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) {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;}
};

5 二叉搜索树中的插入操作

在这里插入图片描述
我们不一定需要按照修改树结构的方式来插入元素，可以直接搜索之后然后再插入相应的结点：
递归法插入结点：
（1）TreeNode* insertIntoBST(TreeNode* root, int val)
（2）终止条件就是找到遍历的节点为null的时候，就是要插入节点的位置了，并把插入的节点返回：

if (root == NULL) {TreeNode* node = new TreeNode(val);return node;
}

（3）根据插入元素的值来返回递归的方向：

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

最终代码：

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;}
};

也可以利用双指针进行迭代计算：

class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if (root == NULL) {TreeNode* node = new TreeNode(val);return node;}TreeNode* cur = root;TreeNode* parent = root; // 这个很重要，需要记录上一个节点，否则无法赋值新节点while (cur != NULL) {parent = cur;if (cur->val > val) cur = cur->left;else cur = cur->right;}TreeNode* node = new TreeNode(val);if (val < parent->val) parent->left = node;// 此时是用parent节点的进行赋值else parent->right = node;return root;}
};

6 删除二叉搜索树中的节点

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

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

首先找到需要删除的节点； 如果找到了，删除它。 说明： 要求算法时间复杂度为 O ( h ) O(h) O(h)，h 为树的高度。

示例:
在这里插入图片描述
递归法分析
（1）前两个条件都很好分析，这里直接给出：

TreeNode* deleteNode(TreeNode* root, int key)

if (root == nullptr) return root;
（2）单层逻辑：
这里就把二叉搜索树中删除节点遇到的情况都搞清楚。

有以下五种情况：

  • 第一种情况：没找到删除的节点，遍历到空节点直接返回了
  • 找到删除的节点
    • 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
    • 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
    • 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
    • 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。（说人话就是：把删除结点的左子树放到右子树的最左端上）

整体代码：

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的右孩子作为新rootdelete 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;}
};

7 修剪二叉搜索树

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

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

示例 1：
输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]
示例 2：
输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]

递归三部曲
（1）确认递归函数的参数以及返回值
需要对整棵树进行遍历，返回的是节点，通过递归函数的返回值来移除节点。TreeNode* trimBST(TreeNode* root, int low, int high)
（2）确认终止条件
并不需要在终止条件下进行，只需要遇到空节点返回即可。if(root == nullptr) return nullptr
（3）单层逻辑
需要判断，如果当前节点root的元素小于low的数值，那么应该递归右子树，并且返回右子树符合条件的头结点。

if(root->val < low){TreeNode* right = trimBST(root->right, low, high);return right;
}

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

if(root->val > high){TreeNode* left = trimBST(root->left, low, high);return left;
}

接着我们需要将下一层处理完左子树的结果给root->left，右子树的结果给root->right

root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
return root;

整体代码：

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;}

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

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
在这里插入图片描述
本题要构造二叉树，依然用递归函数的返回值来构造中节点的左右孩子。因此需要传入数组，然后传入左右下标。TreeNode* traversal(vector<int>& nums, int left, int right)。定义左闭右闭区间，当区间left>right的时候就是空节点。if(left > right) return nullptr;

那么需要确认单层递归的逻辑，首先取数组中间元素的位置，取中间位置，以中间位置元素构造节点。接着划分区间，root的左孩子接往下一层左区间的构造节点，右孩子接往下一层右区间构造的节点。最后返回root节点。

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;

递归代码：

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;}
};

这篇关于代码随想录 打卡day23，24，25的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/985827。

相关文章

活用c4d官方开发文档查询代码

活用c4d官方开发文档查询代码

当你问AI助手比如豆包，如何用python禁止掉xpresso标签时候，它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来
阅读更多...
poj 1258 Agri-Net（最小生成树模板代码）

poj 1258 Agri-Net（最小生成树模板代码）

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码：效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n
阅读更多...
计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者：计算机编程-吉哥 🍊简介：专业从事JavaWeb程序开发，微信小程序开发，定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事，生活就是快乐的。 🍊心愿：点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能
阅读更多...
代码随想录冲冲冲 Day39 动态规划Part7

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d
阅读更多...
pip-tools：打造可重复、可控的 Python 开发环境，解决依赖关系，让代码更稳定

pip-tools：打造可重复、可控的 Python 开发环境，解决依赖关系，让代码更稳定

在 Python 开发中，管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等，都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools？ pip-tools 是一组命令行工具，旨在简化 Python 依赖关系的管理，确保项目环境的稳定性和可重复性。它主要包含两个核心工具：pip-compile 和 pip
阅读更多...
D4代码AC集

D4代码AC集

贪心问题解决的步骤： （局部贪心能导致全局贪心）    1.确定贪心策略    2.验证贪心策略是否正确 排队接水 #include<bits/stdc++.h>using namespace std;int main(){int w,n,a[32000];cin>>w>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);int i=1
阅读更多...
html css jquery选项卡 代码练习小项目

html css jquery选项卡 代码练习小项目

在学习 html 和 css jquery 结合使用的时候 做好是能尝试做一些简单的小功能，来提高自己的 逻辑能力，熟悉代码的编写语法 下面分享一段代码 使用html css jquery选项卡 代码练习 <div class="box"><dl class="tab"><dd class="active">手机</dd><dd>家电</dd><dd>服装</dd><dd>数码</dd><dd
阅读更多...
生信代码入门：从零开始掌握生物信息学编程技能

生信代码入门：从零开始掌握生物信息学编程技能

少走弯路,高效分析;了解生信云,访问 【生信圆桌x生信专用云服务器】 : www.tebteb.cc 介绍 生物信息学是一个高度跨学科的领域，结合了生物学、计算机科学和统计学。随着高通量测序技术的发展，海量的生物数据需要通过编程来进行处理和分析。因此，掌握生信编程技能，成为每一个生物信息学研究者的必备能力。 生信代码入门，旨在帮助初学者从零开始学习生物信息学中的编程基础。通过学习常用
阅读更多...
husky 工具配置代码检查工作流：提交代码至仓库前做代码检查

husky 工具配置代码检查工作流：提交代码至仓库前做代码检查

提示：这篇博客以我前两篇博客作为先修知识，请大家先去看看我前两篇博客 博客指路：前端 ESlint 代码规范及修复代码规范错误-CSDN博客前端 Vue3 项目开发—— ESLint & prettier 配置代码风格-CSDN博客 husky 工具配置代码检查工作流的作用 在工作中，我们经常需要将写好的代码提交至代码仓库 但是由于程序员疏忽而将不规范的代码提交至仓库，显然是不合理的 所
阅读更多...
Unity3D自带Mouse Look鼠标视角代码解析。

Unity3D自带Mouse Look鼠标视角代码解析。

Unity3D自带Mouse Look鼠标视角代码解析。 代码块 代码块语法遵循标准markdown代码，例如： using UnityEngine;using System.Collections;/// MouseLook rotates the transform based on the mouse delta./// Minimum and Maximum values can
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2