网站备案期间可以建站,给别人做的网站要复杂做安全扫描,淄博网站建设同圈科技,安卓优化大师官网下载代码随想录算法训练营
—day18 文章目录 代码随想录算法训练营前言一、530.二叉搜索树的最小绝对差递归法迭代法 二、501.二叉搜索树中的众数普通二叉树的方法递归法中序迭代法 三、 236. 二叉树的最近公共祖先递归法 总结 前言
今天是算法营的第18天#xff0c;希望自己能够…代码随想录算法训练营
—day18 文章目录 代码随想录算法训练营前言一、530.二叉搜索树的最小绝对差递归法迭代法 二、501.二叉搜索树中的众数普通二叉树的方法递归法中序迭代法 三、 236. 二叉树的最近公共祖先递归法 总结 前言
今天是算法营的第18天希望自己能够坚持下来 今日任务 ● 530.二叉搜索树的最小绝对差 ● 501. 二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先 一、530.二叉搜索树的最小绝对差 题目链接 文章讲解 视频讲解 思路 二叉搜索树的特点中序遍历得出递增的数组。 因此最小绝对差就会出现在相邻的两个元素之间。 使用双指针的方法一前一后指向树的两个节点记录最小绝对差。
递归法
递归函数的参数和返回值参数当前传入节点。 返回值用一个全局变量存储最小绝对差所以不需要返回值。终止条件遇到空节点了为终止。单层递归的逻辑递归左节点计算当前节点和上一个节点的差记录最小值递归右节点
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int result INT_MAX;TreeNode* pre nullptr; //指向上一个节点//使用双指针和中序遍历计算相邻的两个节点的差记录最小值void traversal(TreeNode* cur) {if (cur nullptr) return;traversal(cur-left);//左if (pre ! nullptr) result min(result, cur-val - pre-val); //中pre cur;//更新pre指针traversal(cur-right);//右return;}int getMinimumDifference(TreeNode* root) {traversal(root);return result;}
};迭代法
使用中序迭代法模板也可以做。 代码如下
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int getMinimumDifference(TreeNode* root) {int result INT_MAX;TreeNode* pre nullptr;stackTreeNode* st;TreeNode* cur root;while (cur ! nullptr || !st.empty()) {if (cur ! nullptr) { // 指针来访问节点访问到最底层st.push(cur); // 将访问的节点放进栈cur cur-left; //左} else {cur st.top();st.pop();if (pre ! nullptr) { //中result min(result, cur-val - pre-val);}pre cur;cur cur-right; //右}}return result;}
};二、501.二叉搜索树中的众数 题目链接 文章讲解 视频讲解 普通二叉树的方法
思路
遍历二叉树将每个元素和出现的次数记录在map中将map转成vector定义一个cmp函数将vector用sort按降序排序取vector的第一个元素然后遍历vector看是否还有出现频率相同的其他元素。
代码如下
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
private:void searchBST(TreeNode* cur, unordered_mapint,int map) {if (cur nullptr) return;map[cur-val];searchBST(cur-left, map);searchBST(cur-right, map);}//这里定义成static调用的时候就不需要对象bool static cmp (const pairint,int a, const pairint,int b) { return a.second b.second;}public:vectorint findMode(TreeNode* root) {unordered_mapint, int map;vectorint result;if (root nullptr) return result;searchBST(root, map); //遍历二叉树将元素出现频率保存在map中vectorpairint,int vec(map.begin(), map.end()); //将map转成vector来排序sort(vec.begin(), vec.end(), cmp); //排序ab返回truea在前面降序result.push_back(vec[0].first);for (int i 1; i vec.size(); i) {if (vec[i].second vec[0].second) result.push_back(vec[i].first);else break;}return result;}
};递归法
跟上一题计算最小绝对差一样可以使用双指针的方法因为是二叉搜索树按照中序遍历相同节点值只会是相邻的节点。
递归函数的参数和返回值参数当前传入节点。 返回值用一个全局变量存储结果集所以不需要返回值。终止条件遇到空节点了为终止。单层递归的逻辑递归左节点 ·用count变量统计当前遍历元素的频率用MaxCount保存最大频率 ·如果当前节点是第一个节点count1如果pre curcount ·如果pre cur说明是新的元素重新从1开始计数count1 ·并且通过比较count和MaxCount的大小实时更新结果集 · 当MaxCount更新之后需要对根据旧MaxCount保存下来的结果集清空重新放入新的元素 ·递归右节点
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int MaxCount 0; //最大频率int count 0; //统计频率vectorint result;TreeNode* pre nullptr;void traversal(TreeNode* cur) {if (cur nullptr) return;traversal(cur-left); //左//中if (pre nullptr) count 1; //第一个节点else if (pre-val cur-val) count; //上一个节点跟当前节点相同else count 1; //上一个节点跟当前节点不相同pre cur; //更新上一个节点if (count MaxCount) result.push_back(cur-val); //如果和最大值相等放入结果集if (count MaxCount) { //当目前元素出现的次数比最大值高清空之前的结果集把当前元素放入结果集MaxCount count; //更新最大频率result.clear();result.push_back(cur-val);}traversal(cur-right); //右}vectorint findMode(TreeNode* root) {if (root nullptr) return result;traversal(root);return result;}
};中序迭代法
套用中序迭代法的模版对于中间节点的处理跟递归法是一样的。代码如下
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vectorint findMode(TreeNode* root) {int count 0; //统计频率int MaxCount 0; //最大频率vectorint result;TreeNode* pre nullptr;stackTreeNode* st;TreeNode* cur root;//中序迭代法向左遍历将遍历过的元素放入栈中直到空节点了再将栈中节点取出处理然后向右遍历//其余思路跟递归法一样用双指针while (cur ! nullptr || !st.empty()) {if (cur ! nullptr) {st.push(cur); //指针访问节点访问到最底层cur cur-left; //左} else {cur st.top();st.pop();//中if (pre nullptr) count 1; //第一个节点else if (pre-val cur-val) count; //与前一个节点数值相同else count 1; //与前一个节点数值不同pre cur; //更新前一个节点if (count MaxCount) result.push_back(cur-val); //如果和最大值相同放入结果集if (count MaxCount) { //如果计数大于最大值频率MaxCount count; //更新最大频率result.clear(); //清空之前最大值频率存的结果集result.push_back(cur-val); //放入当前频率最大的值}cur cur-right; //右}}return result;}
};三、 236. 二叉树的最近公共祖先 题目链接 文章讲解 视频讲解 情况一如果找到一个节点发现左子树出现结点p右子树出现节点q或者 左子树出现结点q右子树出现节点p那么该节点就是节点p和q的最近公共祖先 情况二节点本身p(q)它拥有一个子孙节点q§
思路 需要从下往上返回结果才知道p和q的共同祖先是谁。使用后序遍历将左节点和右节点的结果返回给中间节点。
完整过程如下
递归法
递归函数的参数和返回值传入树的根节点递归函数的返回值为数值之和终止条件如果遍历到空节点那么左叶子值一定是0只有当前遍历的节点是父节点才能判断其子节点是不是左叶子。如果当前遍历的节点是叶子节点那其左叶子也必定是0单层递归的逻辑当遇到左叶子节点的时候记录数值然后通过递归求取左子树左叶子之和和 右子树左叶子之和相加便是整个树的左叶子之和。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public://后序递归//回溯的思想当找到p和q的时候返回节点给上一层此时返回的是p和q的位置//上一层同时获取到p和q的节点那么说明当前节点就是最近公共祖先//将该节点继续返回给上层此时返回的是公共祖先TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//当root为空返回空找到p或者q节点向上返回if (!root || root p || root q) return root;TreeNode* left lowestCommonAncestor(root-left, p, q); //向左遍历找p或q或者公共祖先TreeNode* right lowestCommonAncestor(root-right, p, q);//向右遍历找p或q或者公共祖先if (left right) return root; //p和q分别在当前节点左右侧说明当前节点是公共祖先else if (!left right) return right; //只在右节点发现p或者q,或者公共祖先在右节点将结果返回上层else if (left !right) return left; //只在左节点发现p或者q,或者公共祖先在右节点将结果返回上层else return nullptr;}
};总结
今天主要是学习了 1.搜索二叉树的对相邻两个节点值的操作可以使用双指针的方式一前一后操作。 2.通过使用一直清空和更新结果集可以将本来需要遍历两次的功能只用一次就完成了。 3.有递归就有回溯从下往上返回结果要用后序遍历也就是回溯的思想。
明天继续加油
