侧边栏壁纸
博主头像
thinkTV博主等级

喜爱动漫的二刺螈一枚,摩托车云爱好者(快要有车了)。 懂一点技术的在读生物医学工程研究生( •̀ ω •́ )✧,多多指教。

  • 累计撰写 127 篇文章
  • 累计创建 17 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

代码随想录算法训练营第二十一天 | 二叉搜索树的最小绝对差;二叉搜索树中的众数;二叉树的最近公共祖先

thinkTV
2023-05-09 / 0 评论 / 0 点赞 / 118 阅读 / 2,093 字 / 正在检测是否收录...

1. 二叉搜索树的最小绝对差

代码随想录: 原文

力扣题目:530.二叉搜索树的最小绝对差

1.1 思路

  • 注意是二叉搜索树,二叉搜索树可是有序的
  • 遇到在二叉搜索树上求什么最值,差值之类的,就把它想成在一个有序数组上求最值,求差值
  • 最直观的想法,就是把二叉搜索树转换成有序数组,然后遍历一遍数组,就统计出来最小差值了

在二叉搜素树中序遍历的过程中,直接计算差值,使用双指针法

  • 需要用一个pre节点记录一下cur节点的前一个节点

图片-1683624017936

2.2 代码实现

转换为有序数组

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;
    }
};

直接在遍历中计算

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;
    }
};

2. 二叉搜索树中的众数

代码随想录: 原文

力扣题目:501.二叉搜索树中的众数

2.1 思路

2.1.1 如果不是二叉搜索树

这个树都遍历了,用map统计频率,把频率排个序,最后取前面高频的元素的集合

1. 遍历二叉树,用map统计频率

// map<int, int> key:元素,value:出现频率
void searchBST(TreeNode* cur, unordered_map<int, int>& map) { // 前序遍历
    if (cur == NULL) return ;
    map[cur->val]++; // 统计元素频率
    searchBST(cur->left, map);
    searchBST(cur->right, map);
    return ;
}

2. 把统计的出来的出现频率(即map中的value)排个序

  • 把map转化数组即vector,再进行排序
  • vector里面放的也是pair<int, int>类型的数据,第一个int为元素,第二个int为出现频率
bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {
    return a.second > b.second; // 按照频率从大到小排序
}

vector<pair<int, int>> vec(map.begin(), map.end());
sort(vec.begin(), vec.end(), cmp); // 给频率排个序

3. 取前面高频的元素

  • 数组vector中已经是存放着按照频率排好序的pair
  • 把前面高频的元素取出来就可以了
result.push_back(vec[0].first);
for (int i = 1; i < vec.size(); i++) {
    // 取最高的放到result数组中
    if (vec[i].second == vec[0].second) result.push_back(vec[i].first);
    else break;
}
return result;

2.1.2 是二叉搜索树

是搜索树,它中序遍历就是有序的

中序遍历代码如下:

void searchBST(TreeNode* cur) {
    if (cur == NULL) return ;
    searchBST(cur->left);       // 左
    (处理节点)                // 中
    searchBST(cur->right);      // 右
    return ;
}

  • 弄一个指针指向前一个节点,这样每次cur(当前节点)才能和pre(前一个节点)作比较
  • 而且初始化的时候pre = NULL,这样当pre为NULL时候,我们就知道这是比较的第一个元素
  • 频率count 等于 maxCount(最大频率),当然要把这个元素加入到结果集中
  • 频率count 大于 maxCount的时候,不仅要更新maxCount,而且要清空结果集
if (count == maxCount) { // 如果和最大值相同,放进result中
    result.push_back(cur->val);
}
if (count > maxCount) { // 如果计数大于最大值
    maxCount = count;   // 更新最大频率
    result.clear();     // 很关键的一步,不要忘记清空result,之前result里的元素都失效了
    result.push_back(cur->val);
}

2.2 代码实现

不是二叉搜索树

class Solution {
private:

void searchBST(TreeNode* cur, unordered_map<int, int>& map) { // 前序遍历
    if (cur == NULL) return ;
    map[cur->val]++; // 统计元素频率
    searchBST(cur->left, map);
    searchBST(cur->right, map);
    return ;
}
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; // key:元素,value:出现频率
        vector<int> result;
        if (root == NULL) return result;
        searchBST(root, map);
        vector<pair<int, int>> vec(map.begin(), map.end());
        sort(vec.begin(), vec.end(), cmp); // 给频率排个序
        result.push_back(vec[0].first);
        for (int i = 1; i < vec.size(); i++) {
            // 取最高的放到result数组中
            if (vec[i].second == vec[0].second) result.push_back(vec[i].first);
            else break;
        }
        return result;
    }
};

是二叉搜索树

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) { // 第一个节点
            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;
        TreeNode* pre = NULL; // 记录前一个节点
        result.clear();

        searchBST(root);
        return result;
    }
};

3. 二叉树的最近公共祖先

代码随想录: 原文

力扣题目:236. 二叉树的最近公共祖先

3.1 思路

  • 后序遍历(左右中)就是天然的回溯过程,可以根据左右子树的返回值,来处理中节点的逻辑
  • 如果找到一个节点,发现左子树出现结点p,右子树出现节点q,或者 左子树出现结点q,右子树出现节点p,那么该节点就是节点p和q的最近公共祖先:

图片-1683628664289

  • 就是节点本身p(q),它拥有一个子孙节点q§:

图片-1683628690884

递归三部曲:

1. 确定递归函数返回值以及参数

  • 返回值为bool类型
  • 返回最近公共节点,可以利用上题目中返回值是TreeNode *
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)

2. 确定终止条件

  • 如果 root == q,或者 root == p,说明找到 q p ,则将其返回
if (root == q || root == p || root == NULL) return root;

3. 确定单层递归逻辑

在回溯的过程中,必然要遍历整棵二叉树,即使已经找到结果了,依然要把其他节点遍历完,因为要使用递归函数的返回值(也就是代码中的left和right)做逻辑判断

  • 那么先用left和right接住左子树和右子树的返回值
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
  • 如果left 和 right都不为空,说明此时root就是最近公共节点。这个比较好理解
  • 如果left为空,right不为空,就返回right,说明目标节点是通过right返回的,反之依然
  • 如果left和right都为空,返回空
if (left == NULL && right != NULL) return right;
else if (left != NULL && right == NULL) return left;
else  { //  (left == NULL && right == NULL)
    return NULL;
}


3.2 代码实现

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == q || root == p || root == NULL) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left != NULL && right != NULL) return root;

        if (left == NULL && right != NULL) return right;
        else if (left != NULL && right == NULL) return left;
        else  { //  (left == NULL && right == NULL)
            return NULL;
        }

    }
};

4. 总结

  • 注意二叉搜索树,二叉搜索树可是有序的
  • 双指针的灵活应用
  • 在递归函数有返回值的情况下:如果要搜索一条边,递归函数返回值不为空的时候,立刻返回,如果搜索整个树,直接用一个变量left、right接住返回值,这个left、right后序还有逻辑处理的需要,也就是后序遍历中处理中间节点的逻辑(也是回溯)。

学习时间:180min

0

评论区