算法训练 | 二叉树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;}
};

（说明：基于代码随想录课程学习，部分内容引用代码随想录文章）