二叉树练习day.8

235.二叉搜索树的最近公共祖先

链接:. - 力扣(LeetCode)

题目描述:

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

示例 1:

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2:

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出:5
解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3:

输入:root = [1,2], p = 1, q = 2
输出:1

提示:

  • 树中节点数目在范围 [2, 105] 内。
  • -109 <= Node.val <= 109
  • 所有 Node.val 互不相同
  • p != q
  • pq 均存在于给定的二叉树中。

思路:

根据搜索二叉树的性质可知道,当p小于某个节点的值,而q大于某个节点的值时,该节点就是这个二叉树的最近公共祖先

使用递归实现:

1.确定函数的参数和返回值,函数的参数应该为二叉树的根节点以及p和q,返回值应该为要找到的公共祖先

2.确定递归终止逻辑,如果节点为空,则返回空,如果当前结点的大于p且当前节点小于q,则该节点就是最近公共祖先,返回该节点

3.确定递归的单层逻辑,根据二叉搜索树的性质,可知遍历的方向,如果p和q都小于当前节点,则向左去遍历,否则向右去遍历

代码实现:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if(root == NULL)
        return NULL;
    if(root->val > p->val && root->val < q->val)
        return root;
    
    if(root->val > p->val && root->val > q->val)
    {
        struct TreeNode *left = lowestCommonAncestor(root->left,p,q);
        return left;
    }
    if(root->val < p->val && root->val < q->val)
    {
        struct TreeNode *right = lowestCommonAncestor(root->right,p,q);
        return right;
    }
    return root;
}

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

链接:. - 力扣(LeetCode)

题目描述:

给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value ,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。

注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果

示例 1:

输入:root = [4,2,7,1,3], val = 5
输出:[4,2,7,1,3,5]
解释:另一个满足题目要求可以通过的树是:

示例 2:

输入:root = [40,20,60,10,30,50,70], val = 25
输出:[40,20,60,10,30,50,70,null,null,25]

示例 3:

输入:root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出:[4,2,7,1,3,5]

提示:

  • 树中的节点数将在 [0, 104]的范围内。
  • -108 <= Node.val <= 108
  • 所有值 Node.val 是 独一无二 的。
  • -108 <= val <= 108
  • 保证 val 在原始BST中不存在。

思路:

因为题目要求的插入节点之后依旧是二叉搜索树的结构,因此我们可以想到将要插入的节点插入到叶子节点上,这样会更容易实现,不会改变原树的结构

递归实现:

1.确定函数的参数和返回值,函数的参数应该是二叉搜索树的根节点已经要插入的值,返回值应该为插入节点后的二叉树

2.确定递归终止条件,当我们找到适合插入的位置时,进行插入操作之后就返回该插入的节点,这个节点的信息就会传递给它的父节点

3.确定单层递归逻辑,判断要插入的值与当前节点的值的大小,如果大于当前节点的值,则遍历左子树,否则遍历右子树

代码实现:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {
    //符合条件的位置
    if(!root)
    {
        //此时node为叶子节点,注意设置叶子节点在左右子树为空
        struct TreeNode *node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
        node->val = val;
        node->left = NULL;
        node->right = NULL;
        return node;
    }

    if(root->val > val)
        root->left = insertIntoBST(root->left, val);
    else
        root->right = insertIntoBST(root->right, val);


    return root;
}

450.删除二叉搜索树中的节点

链接:. - 力扣(LeetCode)

题目描述:

给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说,删除节点可分为两个步骤:

  1. 首先找到需要删除的节点;
  2. 如果找到了,删除它。

示例 1:

输入:root = [5,3,6,2,4,null,7], key = 3
输出:[5,4,6,2,null,null,7]
解释:给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。


示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3:

输入: root = [], key = 0
输出: []

提示:

  • 节点数的范围 [0, 104].
  • -105 <= Node.val <= 105
  • 节点值唯一
  • root 是合法的二叉搜索树
  • -105 <= key <= 105

思路:

我们可以根据二叉搜索树的性质去查找二叉搜索树中要删除的值,不需要遍历整个二叉树,在搜索过程中,我们可以想到几种情况,分别是

1.没有找到我们要删除的值

2.找到了我们要删除的节点,该节点为叶子节点

3.找到了要删除的节点,该节点的左子树不为空,右子树为空

4.找到了要删除的节点,该节点左子树为空,右子树不为空

5.找到要删除的节点,该节点左右子树都不为空,需要对该节点的左右子树做出判断

递归实现思路:

1.确定函数的参数和返回值,函数的参数应该是我们要传入的二叉树已经要删除的值,返回值应该为删除节点后的二叉树

2.确定递归函数的终止条件:

当没有找到这个节点时,遇到空节点直接返回

当要删除的节点为叶子节点时,因为使用递归,返回NULL(其父节点接收该节点的位置变为空),释放该节点所占的内存空间

当要删除的节点有左子树没有右子树,进行删除操作,返回删除节点的左孩子,删除节点的父节点会接收删除节点的左孩子,进行内存释放

当要删除的节点没有左子树有右子树,进行删除操作,返回删除节点的右孩子,删除节点的父节点会接收删除节点的右孩子,进行内存释放

当删除的节点有左孩子也有右孩子,先找到其右孩子,再一直向左遍历,找到删除节点的右子树的最左叶子节点,将删除节点的左子树插入到最左叶子节点之后,这样不会改变二叉搜索树的结构

3.确定单层递归逻辑,根据要删除的值判断往左或右去查找

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* deleteNode(struct TreeNode* root, int key){
    //没有找到
    if(!root)
        return root;
    //找到
    if(root->val == key)
    {
        if(!root->left && !root->right)
        {
            //释放root,并让root的父节点指向空
            free(root);
            return NULL;
        }
        else if(root->left && !root->right)
        {
            //记录root左子树,并返回该子树给删除节点的父节点
            struct TreeNode *tem = root->left;
            free(root);
            return tem;
        }
        else if(!root->left && root->right)
        {
            //记录root右子树,并返回该子树给删除节点的父节点
            struct TreeNode *tem = root->right;
            free(root);
            return tem;
        }
        else
        {
            //记录root右子树,并返回该子树给删除节点的父节点
            struct TreeNode *cur = root->right;
            //找到右子树最左的叶子节点
            while(cur->left)
            {
                cur = cur->left;
            }
            //要删除节点的左子树连接到右子树最左的叶子节点
            cur->left = root->left;
            struct TreeNode *tem = root->right;
            free(root);
            return tem;
        }
    }
    //递归遍历
    if(root->val > key)
        root->left = deleteNode(root->left,key);
    else
        root->right = deleteNode(root->right,key);

    return root;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/540466.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

一起找bug之购物

如果不是购物车满了&#xff0c;大概都不会发现这个 bug 淘宝 APP 修复了购物车满的情况下&#xff0c;往里面添加新商品时&#xff0c;会把一个老商品移入收藏夹&#xff0c; 但是如果这个老商品是已失效状态&#xff0c;就无法自动移入收藏夹&#xff0c;而且会一直在购物车…

AI禁区徘徊监测识别摄像机

AI禁区徘徊监测识别摄像机是一种基于人工智能技术的智能监控设备&#xff0c;用于监测禁止进入或逗留的区域。这种摄像机通过高清摄像头实时捕捉场景图像&#xff0c;利用AI算法对人员徘徊行为进行识别和监测&#xff0c;有助于提高安全防范水平&#xff0c;减少潜在的安全风险…

【DL水记】循环神经网络RNN的前世今生,Transformer的崛起,Mamba模型

文章目录 RNN网络简介传统RNN网络结构RNN的分类 长-短期记忆网络 (LSTM)GRU网络横空出世的Transformer网络Self-AttentionVisionTransformer Mamba模型Reference: RNN网络简介 “当人类接触新事物时&#xff0c;他们不会从头开始思考。就像你在阅读这篇文章时&#xff0c;你会根…

基于springboot仿雀语的文档管理系统

项目介绍 本项目借鉴了雀语的一些UI设计&#xff0c;实现了文档在线管理的功能&#xff0c;知识库可以对不同分类的文档建立不同的库&#xff0c;知识库里面左边可以维护菜单菜单目录&#xff0c;右边实现在线预览。该项目可以防止用户下载和复制文档&#xff0c;只支持在线预…

Excel从零基础到高手【办公】

第1课 - 快速制作目录【上篇】第1课 - 快速制作目录【下篇】第2课 - 快速定位到工作表的天涯海角第3课 - 如何最大化显示工作表的界面第4课 - 给你的表格做个瘦身第5课 - 快速定位目标区域所在位置第6课 - 快速批量填充序号第7课 - 按自定义的序列排序第8课 - 快速删除空白行第…

接招吧! selenium环境+元素定位大法

selenium 与 webdriver Selenium 是一个用于 Web 测试的工具&#xff0c;测试运行在浏览器中&#xff0c;就像真正的用户在手工操作一样。支持所有主流浏览器 WebDriver 就是对浏览器提供的原生API进行封装&#xff0c;使其成为一套更加面向对象的Selenium WebDriver API。 …

UltraScale 架构 SelectIO 资源之IODELAY与IOSERDES仿真与使用

平台&#xff1a;vivado2018.3 具体内容见ug571-ultrascale-selectio IDELAYE3 在调试超高速信号的时候&#xff0c;需要使用iodelayiserdes来调试校准输入信号。例如外部某ADC采样率为5GHZ&#xff0c;外部ADC使用2.5GHZ的时钟去采集输入信号。为了实现采集&#xff0c;adc芯…

普乐蛙VR航天体验馆设备VR太空飞船VR元宇宙展厅

三天小长假就要来啦&#xff01;五一假期也即将到来。老板们想捉住人流量这个财富密码吗&#xff1f;那快快行动起来&#xff01;开启VR体验项目&#xff0c;假期赚翻天&#xff01;小编亲测&#xff01;&#xff01;这款设备刺激好玩&#xff0c;想必会吸引各位家长小孩、学生…

Normalization

Norm介绍 归一化层&#xff0c;目前主要有这几个方法&#xff0c;Batch Normalization&#xff08;2015年&#xff09;、Layer Normalization&#xff08;2016年&#xff09;、Instance Normalization&#xff08;2017年&#xff09;、Group Normalization&#xff08;2018年&…

【研发日记】CANoe自动化测试的配置方式(三)——SystemVariables数组方式

文章目录 前言 一、例程功能 二、仿真ECU 三、SystemVariables数组&#xff1a; 四、测试模块 五、测试运行效果 六、分析和应用 总结 前言 近期在做的一个自动化测试项目&#xff0c;尝试了一种以前没用过的测试配置方式&#xff0c;感觉效果还不错。然后又回顾了一下以…

php其他反序列化知识学习

简单总结一下最近学习的&#xff0c;php其他的一些反序列化知识 phar soap session 其他 __wakeup绕过gc绕过异常非公有属性&#xff0c;类名大小写不敏感正则匹配&#xff0c;十六进制绕过关键字检测原生类的利用 phar 基础知识 在 之前学习的反序列化利用中&#xff0…

Golang | Leetcode Golang题解之第19题删除链表的倒数第N个结点

题目&#xff1a; 题解&#xff1a; func removeNthFromEnd(head *ListNode, n int) *ListNode {dummy : &ListNode{0, head}first, second : head, dummyfor i : 0; i < n; i {first first.Next}for ; first ! nil; first first.Next {second second.Next}second.N…

谷歌推出适用于安卓设备的“Find My Device”网络,功能类似苹果Find My

谷歌今日推出了适用于安卓设备的“Find My Device”网络&#xff0c;其功能类似于苹果的“Find My”网络&#xff0c;旨在帮助用户定位丢失、被盗的安卓产品。 安卓的“Find My Device”网络可以利用数以亿计运行 Android 9 或更高版本的安卓设备&#xff0c;通过蓝牙信号追踪丢…

Golang ProtoBuf 初学者完整教程:语法

一、编码规范推荐 1、文件名使用小写下划线的命名风格&#xff0c;例如 lower_snake_case.proto 2、使用 2 个空格缩进 3、包名应该和目录结构对应 4、消息名使用首字母大写驼峰风格(CamelCase)&#xff0c;例如message StudentRequest { ... } 5、字段名使用小写下划线的风格…

内网通如何去除广告,内网通免广告生成器

公司使用内网通内部传输确实方便&#xff01;但是会有广告弹窗推送&#xff01;这个很烦恼&#xff01;那么如何去除广告呢&#xff01; 下载&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1CVVdWexliF3tBaFgN1W9aw?pwdhk7m 提取码&#xff1a;hk7m ID&#xff1a;…

数据结构之来链表——单链表

什么是单链表&#xff1a; 文字说明&#xff1a; 单链表顾名思义&#xff0c;就是指单项链表&#xff0c;即只有一个方向的链性线性表。 图解&#xff1a; 如下图所示&#xff0c;即为链表&#xff08;DATA为我们自己所定义的数据类型&#xff09;&#xff1a; 单链表的创建&am…

酷柚易讯无人共享空间单开版安装说明

1、安装环境准备 PHP环境7.4 mysql数据库需要5.7 同时需要安装宝塔面板&#xff08;&#xff57;&#xff57;&#xff57;&#xff0e;&#xff42;&#xff54;&#xff0e;&#xff43;&#xff4e;&#xff09; &#xff12;、获取系统安装包 联系工作人员获取安装包后…

面试:线程和线程池

目录 目标 一、线程有哪些状态 1、新建态&#xff08;NEW&#xff09;&#xff1a; 2、可运行态&#xff08;RUNNABLE&#xff09;&#xff1a; 3、终结态&#xff08;TERMINATED&#xff09;&#xff1a; 4、阻塞态&#xff08;BLOCKED&#xff09;&#xff1a; 5、等待态…

springboot3使用自定义注解+AOP+redis优雅实现防重复提交

⛰️个人主页: 蒾酒 &#x1f525;系列专栏&#xff1a;《spring boot实战》 &#x1f30a;山高路远&#xff0c;行路漫漫&#xff0c;终有归途 目录 写在前面 实现思路 实现步骤 1.定义防重复提交注解 2.编写一个切面去发现该注解然后执行防重复提交逻辑 3.测试 …

VNC Viewer 连接远程主机及常见错误处理(The connection closed unexpectedly)

搭建可接收vnc连接的环境 1、下载镜像 https://github.com/fcwu/docker-ubuntu-vnc-desktop 该镜像是含有ubuntu 通过docker运行的桌面环境&#xff0c;并接受vnc 的连接 docker pull dorowu/ubuntu-desktop-lxde-vnc 2、运行容器 1&#xff09;只暴露容器的80端口&#…