代码随想录打卡DAY20

server/2024/11/28 14:49:59/

算法记录第20天 [二叉树]

1.LeetCode 501. 二叉搜索树中的众数

题目描述:

  • 给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。
  • 如果树中有不止一个众数,可以按 任意顺序 返回。
  • 假定 BST 满足如下定义:
    • 结点左子树中所含节点的值 小于等于 当前节点的值
    • 结点右子树中所含节点的值 大于等于 当前节点的值
    • 左子树和右子树都是二叉搜索树
  • 示例 1:
    在这里插入图片描述
    输入:root = [1,null,2,2]
    输出:[2]

题目链接:https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/

解题步骤 :

  1. 递归过程

    • 中序遍历:首先递归访问左子树,然后处理当前节点,最后递归访问右子树。
    • pre 存储了上一个访问的节点,这样我们就可以比较当前节点和上一个节点的值。如果它们相同,则 count 增加;如果不同,则 count 重置为 1。
  2. 更新结果

    • 每次遇到新的节点时,检查它的出现频率。
    • 如果它的频率等于当前 maxCount,则将其加入 result
    • 如果它的频率大于 maxCount,则更新 maxCount 并清空 result,重新添加当前节点值。
  3. 最终结果:遍历完树后,result 包含了所有出现次数最多的值。

代码:

  int count=1;int maxCount=1;TreeNode* pre=nullptr;vector<int> result;void travseral(TreeNode* cur){// 退出条件if(cur==nullptr) return;travseral(cur->left);// 判断是否和pre相同 count++if(pre==nullptr){count=1;}else if(pre->val == cur->val){count++;}else{count=1;}// 判断maxCount  与resultif(count==maxCount){result.push_back(cur->val);}if(count>maxCount){maxCount=count;result.clear();result.push_back(cur->val);}// 递归pre = cur;travseral(cur->right);}vector<int> findMode(TreeNode* root) {travseral(root);return result;}

2.LeetCode 701. 二叉搜索树中的插入操作

题目描述:

  • 给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value ,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。
  • 注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
  • 示例 1:
    在这里插入图片描述
    输入:root = [4,2,7,1,3], val = 5
    输出:[4,2,7,1,3,5]
    解释:另一个满足题目要求可以通过的树是:
    在这里插入图片描述

题目链接:https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/

解题步骤 :

  1. 递归终止条件:如果当前节点为空 (root == nullptr),我们就创建一个新的节点并返回它。

  2. 递归过程

    • 如果 val 小于当前节点的值 (val < root->val),我们将递归地向左子树插入。
    • 如果 val 大于当前节点的值 (val > root->val),我们将递归地向右子树插入。
  3. 返回根节点:每次递归返回的根节点会更新其父节点的 leftright 指针,从而维持树的结构。

代码:

    TreeNode* parent;void traversal(TreeNode* cur,int val){// 返回条件,插入节点if(cur==nullptr){TreeNode* Node = new TreeNode(val);if (val > parent->val) parent->right = Node;else parent->left = Node;return;}//parent = cur;if(cur->val > val) traversal(cur->left,val);if(cur->val < val) traversal(cur->right,val);}TreeNode* insertIntoBST(TreeNode* root, int val) {parent = new TreeNode(0);if (root == NULL) {root = new TreeNode(val);}traversal(root, val);return root;}

3.LeetCode

题目描述:450. 删除二叉搜索树中的节点

  • 给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
  • 一般来说,删除节点可分为两个步骤:
    • 首先找到需要删除的节点;
    • 如果找到了,删除它。

题目链接:https://leetcode.cn/problems/delete-node-in-a-bst/description/

解题步骤 :

  1. 递归终止条件

    • 如果当前节点为空 (root == nullptr),表示没有找到要删除的节点,直接返回 nullptr
  2. 找到了要删除的节点

    • root->val == key 时,表示当前节点就是需要删除的节点。此时需要根据当前节点的子树情况采取不同的删除策略。
  3. 删除节点的不同情况

    • 没有子节点(叶节点):如果当前节点没有左孩子和右孩子,直接删除节点并返回 nullptr
    • 只有右孩子:如果当前节点没有左孩子,但有右孩子,删除当前节点,并将其右孩子替代当前节点。
    • 只有左孩子:如果当前节点没有右孩子,但有左孩子,删除当前节点,并将其左孩子替代当前节点。
    • 左右孩子都不为空:如果当前节点既有左子树又有右子树,那么需要找到右子树中的最小节点(即右子树中最左边的节点),用这个节点替代当前节点的值,并删除右子树中的最小节点。
  4. 递归删除

    • 如果当前节点的值大于 key,则递归删除左子树中的节点。
    • 如果当前节点的值小于 key,则递归删除右子树中的节点。
  5. 返回更新后的树

    • 在递归的每一步中,都需要返回更新后的根节点,以便正确维护树的结构。

代码:

TreeNode* deleteNode(TreeNode* root, int key) {//1、没找到if(root==nullptr) return root;// 找到了删除的节点if(root->val == key){//2、左右孩子节点都空if(!root->left && !root->right){//! 内存释放delete root;return nullptr;}//3、左孩子节点空,右孩子节点不空else if(!root->left ){auto retNode = root->right;//! 内存释放delete root;return retNode;}//4、右孩子节点不空,左孩子节点空else if(!root->right){auto retNode = root->left;//! 内存释放delete root;return retNode;}// 5都不空else{TreeNode* cur = root->right; // 找右子树最左面的节点while(cur->left != nullptr) {cur = cur->left;}cur->left = root->left;TreeNode* tmp = root;   root = root->right;     delete tmp;            return root;}}if (root->val > key) root->left = deleteNode(root->left, key);if (root->val < key) root->right = deleteNode(root->right, key);return root;}

http://www.ppmy.cn/server/145651.html

相关文章

深入解析经典排序算法:原理、实现与优化

文章目录 6. 堆排序&#xff08;Heap Sort&#xff09;原理Java 实现 7. 希尔排序&#xff08;Shell Sort&#xff09;原理Java 实现 8. 计数排序&#xff08;Counting Sort&#xff09;原理Java 实现 9. 基数排序&#xff08;Radix Sort&#xff09;原理Java 实现 深入浅出&am…

(STM32)ADC驱动配置

1.ADC驱动&#xff08;STM32&#xff09; ADC模块中&#xff0c;**常规模式&#xff08;Regular Mode&#xff09;和注入模式&#xff08;Injected Mode&#xff09;**是两种不同的ADC工作模式 常规模式&#xff1a;用于普通的ADC转换&#xff0c;是默认的ADC工作模式。 注入…

【ROS2】ROS2 与 ROS1 编码方式对比(C++实现)

目录 一、初始化和关闭节点二、发布者和订阅者三、服务和客户端四、参数管理五、日志记录六、生命周期管理 ROS1 主要使用roscpp和rospy作为客户端库&#xff0c;分别用于C和Python语言。 ROS2 引入了新的客户端库rclcpp&#xff08;C&#xff09;和rclpy&#xff08;Python&a…

iOS开发之修改已有项目的项目名和类名前缀

一、修改项目名称 1、Xcode打开项目修改项目名称 直接选中项目&#xff0c;点击enter&#xff0c;直接修改项目名称 把buydodo改成xiedodo&#xff0c;点击enter Rename完了点继续&#xff0c;只有框框内的部分变了 2、退出Xcode关闭项目&#xff0c;修改剩下的项目名称 找…

论文笔记(五十七)Diffusion Model Predictive Control

Diffusion Model Predictive Control 文章概括摘要1. Introduction2. Related work3. 方法3.1 模型预测控制3.2. 模型学习3.3. 规划&#xff08;Planning&#xff09;3.4. 适应 4. 实验&#xff08;Experiments&#xff09;4.1. 对于固定奖励&#xff0c;D-MPC 可与其他离线 RL…

element-plus弹窗二次封装踩坑

1 基于element-plus的二次封装弹窗很常见。代码如下&#xff1a; 父组件&#xff1a; import Dialog from ./components/Dialogs/testDailog.vueconst showref(false) const openDialog()>{show.valuetrue}<button click"openDialog" >打开dialoag</bu…

git merge 排除文件

方法一&#xff1a; 在Git中&#xff0c;如果你想在合并时排除特定文件&#xff0c;你可以使用.gitattributes文件来指定合并策略。你可以设置一个自定义合并策略来忽略特定文件的合并。 首先&#xff0c;在仓库的根目录下创建或编辑.gitattributes文件&#xff0c;并添加以…

微服务上下线动态感知实现的技术解析

序言 随着微服务架构的广泛应用&#xff0c;服务的动态管理和监控变得尤为重要。在微服务架构中&#xff0c;服务的上下线是一个常见的操作&#xff0c;如何实时感知这些变化&#xff0c;确保系统的稳定性和可靠性&#xff0c;成为了一个关键技术挑战。本文将深入探讨微服务上…