算法训练 | 二叉树Part7 | 530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数
目录
530.二叉搜索树的最小绝对差
数组法
双指针法 ⭐
迭代法
501.二叉搜索树中的众数
双指针法
迭代法
530.二叉搜索树的最小绝对差
-
题目链接：530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）
-
文章讲解：代码随想录
数组法
-
解题思路
-
把二叉搜索树转换成有序数组，然后遍历一遍数组，就统计出来最小差值了
-
-
代码一：数组
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 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) {stack<TreeNode*> 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;vector<int> 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:vector<int> findMode(TreeNode* root) {count = 0;maxCount = 0;pre = NULL; // 记录前一个节点result.clear();searchBST(root);return result;}
};迭代法
-
解题思路
-
把中序遍历转成迭代，中间节点的处理逻辑完全一样。
-
-
代码一：迭代
class Solution {
public:vector<int> findMode(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur = root;TreeNode* pre = NULL;int maxCount = 0; // 最大频率int count = 0; // 统计频率vector<int> 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;}
};（说明：基于代码随想录课程学习，部分内容引用代码随想录文章）