代码随想录算法训练营day18

代码随想录算法训练营

—day18

---

前言

今天是算法营的第18天，希望自己能够坚持下来！
今日任务：
● 530.二叉搜索树的最小绝对差
● 501. 二叉搜索树中的众数
● 236. 二叉树的最近公共祖先

---

一、530.二叉搜索树的最小绝对差

题目链接
文章讲解
视频讲解

思路：
二叉搜索树的特点，中序遍历得出递增的数组。
因此最小绝对差就会出现在相邻的两个元素之间。
使用双指针的方法，一前一后指向树的两个节点，记录最小绝对差。

递归法

1. 递归函数的参数和返回值：参数：当前传入节点。 返回值：用一个全局变量存储最小绝对差，所以不需要返回值。
2. 终止条件：遇到空节点了为终止。
3. 单层递归的逻辑：递归左节点；计算当前节点和上一个节点的差，记录最小值；递归右节点

/*** 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;stack<TreeNode*> 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.二叉搜索树中的众数

题目链接
文章讲解
视频讲解

普通二叉树的方法

思路：

1. 遍历二叉树，将每个元素和出现的次数记录在map中
2. 将map转成vector，定义一个cmp函数，将vector用sort按降序排序
3. 取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_map<int,int>& map) {if (cur == nullptr) return;map[cur->val]++;searchBST(cur->left, map);searchBST(cur->right, map);}//这里定义成static调用的时候就不需要对象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;vector<int> result;if (root == nullptr) return result;searchBST(root, map); //遍历二叉树将元素出现频率保存在map中vector<pair<int,int>> vec(map.begin(), map.end()); //将map转成vector来排序sort(vec.begin(), vec.end(), cmp); //排序，a>b返回true，a在前面，降序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;}
};

递归法

跟上一题计算最小绝对差一样，可以使用双指针的方法，因为是二叉搜索树，按照中序遍历，相同节点值只会是相邻的节点。

1. 递归函数的参数和返回值：参数：当前传入节点。 返回值：用一个全局变量存储结果集，所以不需要返回值。
2. 终止条件：遇到空节点了为终止。
3. 单层递归的逻辑：递归左节点；
   ·用count变量统计当前遍历元素的频率，用MaxCount保存最大频率，
   ·如果当前节点是第一个节点，count=1，如果pre = cur，count++，
   ·如果pre ！=cur，说明是新的元素，重新从1开始计数，count=1；
   ·并且通过比较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; //统计频率vector<int> 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); //右}vector<int> 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:vector<int> findMode(TreeNode* root) {int count = 0; //统计频率int MaxCount = 0; //最大频率vector<int> result;TreeNode* pre = nullptr;stack<TreeNode*> 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的共同祖先是谁。使用后序遍历，将左节点和右节点的结果返回给中间节点。

完整过程如下：

递归法

1. 递归函数的参数和返回值：传入树的根节点，递归函数的返回值为数值之和
2. 终止条件：如果遍历到空节点，那么左叶子值一定是0；
3. 只有当前遍历的节点是父节点，才能判断其子节点是不是左叶子。
4. 如果当前遍历的节点是叶子节点，那其左叶子也必定是0；
5. 单层递归的逻辑：当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和 右子树左叶子之和，相加便是整个树的左叶子之和。

/*** 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.有递归就有回溯！从下往上返回结果要用后序遍历，也就是回溯的思想。

明天继续加油！