渭南做网站都有哪些,下载百度极速版免费安装,纪检监察信息网站建设,wordpress 评论栏目录
530.二叉搜索树的最小绝对差
数组法
双指针法 ⭐
迭代法
501.二叉搜索树中的众数
双指针法
迭代法 530.二叉搜索树的最小绝对差 题目链接#xff1a;530. 二叉搜索树的最小绝对差 - 力扣#xff08;LeetCode#xff09; 文章讲解#xff1a;代码随想录
数组…目录
530.二叉搜索树的最小绝对差
数组法
双指针法 ⭐
迭代法
501.二叉搜索树中的众数
双指针法
迭代法 530.二叉搜索树的最小绝对差 题目链接530. 二叉搜索树的最小绝对差 - 力扣LeetCode 文章讲解代码随想录
数组法 解题思路 把二叉搜索树转换成有序数组然后遍历一遍数组就统计出来最小差值了 代码一数组
class Solution {
private:
vectorint vec;
void traversal(TreeNode* root) {if (root NULL) return;traversal(root-left);vec.push_back(root-val); // 将二叉搜索树转换为有序数组traversal(root-right);
}
public:int getMinimumDifference(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;}
};
双指针法 ⭐ 解题思路 用一个pre节点记录一下cur节点的前一个节点。在二叉搜素树中序遍历的过程中直接计算。 代码注意 设置函数无返回值只进行遍历 代码一双指针
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 min(result, cur-val - pre-val);}pre cur; // 记录前一个traversal(cur-right); // 右
}
public:int getMinimumDifference(TreeNode* root) {traversal(root);return result;}
};
迭代法 解题思路 用栈模拟中序遍历的迭代法 代码一中序
class Solution {
public:int getMinimumDifference(TreeNode* root) {stackTreeNode* st;TreeNode* cur root;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;}
};
501.二叉搜索树中的众数 题目链接leetcode.cn 文章讲解programmercarl.com
双指针法 解题思路 一个指针指向前一个节点这样每次cur当前节点才能和pre前一个节点作比较。而且初始化的时候pre NULL这样当pre为NULL时候我们就知道这是比较的第一个元素。 解题步骤 中序遍历 最大频率统计 存入众数结果频率count 等于 maxCount最大频率当然要把这个元素加入到结果集中以下代码为result数组 结果更新频率count 大于 maxCount的时候不仅要更新maxCount而且要清空结果集以下代码为result数组因为结果集之前的元素都失效了。 代码注意 if (pre ! nullptr pre-val cur-val) 代码一双指针
class Solution {
private:int maxCount 0; // 最大频率int count 0; // 统计频率TreeNode* pre NULL;vectorint result;void searchBST(TreeNode* cur) {if (cur NULL) return ;searchBST(cur-left); // 左// 中if (pre NULL) { // 第一个节点 // if (pre ! nullptr pre-val cur-val) {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:vectorint findMode(TreeNode* root) {count 0;maxCount 0;pre NULL; // 记录前一个节点result.clear();searchBST(root);return result;}
};
迭代法 解题思路 把中序遍历转成迭代中间节点的处理逻辑完全一样。 代码一迭代
class Solution {
public:vectorint findMode(TreeNode* root) {stackTreeNode* st;TreeNode* cur root;TreeNode* pre NULL;int maxCount 0; // 最大频率int count 0; // 统计频率vectorint result;while (cur ! NULL || !st.empty()) {if (cur ! NULL) { // 指针来访问节点访问到最底层st.push(cur); // 将访问的节点放进栈cur cur-left; // 左} else {cur st.top();st.pop(); // 中if (pre NULL) { // 第一个节点count 1;} else if (pre-val cur-val) { // 与前一个节点数值相同count;} else { // 与前一个节点数值不同count 1;}if (count maxCount) { // 如果和最大值相同放进result中result.push_back(cur-val);}if (count maxCount) { // 如果计数大于最大值频率maxCount count; // 更新最大频率result.clear(); // 很关键的一步不要忘记清空result之前result里的元素都失效了result.push_back(cur-val);}pre cur;cur cur-right; // 右}}return result;}
};
说明基于代码随想录课程学习部分内容引用代码随想录文章
