【牛客面试必刷TOP101】Day25.BM38 在二叉树中找到两个节点的最近公共祖先和BM40 重建二叉树

作者简介:大家好,我是未央;

博客首页:未央.303

系列专栏:牛客面试必刷TOP101

每日一句:人的一生,可以有所作为的时机只有一次,那就是现在!!!!!

文章目录

  • 前言
  • 一、BM38 在二叉树中找到两个节点的最近公共祖先
  • 题目描述
  • 题目解析
  • 二、BM40 重建二叉树
  • 题目描述
  • 题目解析
  • 总结


前言


一、BM38 在二叉树中找到两个节点的最近公共祖先

题目描述

描述:

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2,请找到 o1 和 o2 的最近公共祖先节点。



举例说明:

如当输入{3,5,1,6,2,0,8,#,#,7,4},5,1时,二叉树{3,5,1,6,2,0,8,#,#,7,4}如下图所示:

所以节点值为5和节点值为1的节点的最近公共祖先节点的节点值为3,所以对应的输出为3。

节点本身可以视为自己的祖先.


示例1:


示例2:


题目解析

方法:递归

知识点:二叉树递归

二叉树的递归,则是将某个节点的左子树、右子树看成一颗完整的树,那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题,因此可以自我调用函数不断进入子树。


思路:

我们也可以讨论几种情况:

  • step 1:如果o1和o2中的任一个和root匹配,那么root就是最近公共祖先。
  • step 2:如果都不匹配,则分别递归左、右子树。
  • step 3:如果有一个节点出现在左子树,并且另一个节点出现在右子树,则root就是最近公共祖先.
  • step 4:如果两个节点都出现在左子树,则说明最低公共祖先在左子树中,否则在右子树。
  • step 5:继续递归左、右子树,直到遇到step1或者step3的情况。


二、BM40 重建二叉树

题目描述

描述:

给定节点数为 n 的二叉树的前序遍历和中序遍历结果,请重建出该二叉树并返回它的头结点。



举例说明:

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出如下图所示。


示例1:


示例2:

示例3:


题目解析

方法:递归

知识点:二叉树递归

二叉树的递归,则是将某个节点的左子树、右子树看成一颗完整的树,那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题,因此可以自我调用函数不断进入子树。


思路:

对于二叉树的前序遍历,我们知道序列的第一个元素必定是根节点的值,因为序列没有重复的元素,因此中序遍历中可以找到相同的这个元素,而我们又知道中序遍历中根节点将二叉树分成了左右子树两个部分,如下图所示:

我们可以发现,数字1是根节点,并将二叉树分成了(247)和(3568)两棵子树,而子树的的根也是相应前序序列的首位,比如左子树的根是数字2,右子树的根是数字3,这样我们就可以利用前序遍历序列找子树的根节点,利用中序遍历序列区分每个子树的节点数。


具体做法:

  • step 1:先根据前序遍历第一个点建立根节点。
  • step 2:然后遍历中序遍历找到根节点在数组中的位置。
  • step 3:再按照子树的节点数将两个遍历的序列分割成子数组,将子数组送入函数建立子树。
  • step 4:直到子树的序列长度为0,结束递归。

总结

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

什么是智能合约

前言:在介绍智能合约的前提下,需要先介绍一下区块链 一.什么是区块链 区块链实质上是一个去中心化、分布式的可进行交易的数据库或账本,具有下列典型特征: 去中心化:简单来说,在网络上一个或多个服务器瘫…

IPC对象、消息队列 、共享内存

我要成为嵌入式高手之3月4日Linux高编第十四天!! 消息队列、共享内存、信号灯: 一、IPC对象 内存文件,如何查看? 1、ipcs: 查看系统中的IP对象的消息队列、共享内存、信号灯信息 2、ipcrm:…

蓝桥杯倒计时 41天 - 二分答案-最大通过数-妮妮的月饼工厂

最大通过数 思路&#xff1a;假设左边能通过 x 关&#xff0c;右边能通过 y 关&#xff0c;x∈[0,n]&#xff0c;通过二分&#xff0c;在前缀和中枚举右边通过的关卡数&#xff0c;保存 xy 的最大值。 #include<bits/stdc.h> using namespace std; typedef long long ll…

产品营销展示型wordpress外贸网站模板

工艺品wordpress外贸主题 简约大气的wordpress外贸主题&#xff0c;适合做工艺品进出品外贸的公司官网使用。 https://www.jianzhanpress.com/?p5377 餐饮设备wordpress外贸主题 简洁的wordpress外贸主题&#xff0c;适合食品机械、餐饮设备公司使用。 https://www.jianzh…

洛谷 B3620 x 进制转 10 进制

题目描述 给一个小整数 x 和一个 x 进制的数 S。将 S 转为 10 进制数。对于超过十进制的数码&#xff0c;用 A&#xff0c;B&#xff0c;…… 表示。 输入格式 第一行一个整数 x; 第二行一个字符串 S。 输出格式 输出仅包含一个整数&#xff0c;表示答案。 输入输出样例…

leetcode 移除链表元素

本题中&#xff0c;我们是要移除链表的某一个节点&#xff0c;为了确保统一操作&#xff0c;我们需要使用虚拟头节点&#xff0c;这样我们删除节点的时候&#xff0c;就是把这个要删除的节点&#xff08;当前节点cur&#xff09;的前一个节点pre&#xff0c;使得pre.next指向要…

sqlserver保存微信Emoji表情

首先将数据库字段&#xff0c;设置类型为 nvarchar(200)一个emoji表情&#xff0c;占4字节就可以了&#xff0c;web前端展示不用改任何东西&#xff0c;直接提交数据保存&#xff1b;回显也会没有问题&#xff0c;C#代码不用做任何处理&#xff1b; 不哭不闹要睡觉&#x1f31…

执行一条 select 语句,期间发生了什么?

大家好我是苏麟 , 今天开始又开一个坑 MySQL原理 . 资料来源 : 小林coding 小林官方网站 : 小林coding (xiaolincoding.com) 执行一条 select 语句&#xff0c;期间发生了什么&#xff1f; 学习 SQL 的时候&#xff0c;大家肯定第一个先学到的就是 select 查询语句了&#xff…

UCSF DOCK 分子对接详细案例(04)-基于RDKit描述符的分子从头设计DOCK_D3N

欢迎浏览我的CSND博客&#xff01; Blockbuater_drug …点击进入 文章目录 前言一、 软件及操作环境二、研究目的三、结构文件准备四、 DOCK/RDKit中 de novo design4.1 de novo design - refine_D3N4.2 对输出重新评分 总结参考资料 前言 本文是UCSF DOCK的使用案例分享&…

Windows服务器:通过nginx反向代理配置HTTPS、安装SSL证书

先看下效果&#xff1a; 原来的是 http&#xff0c;配置好后 https 也能用了&#xff0c;并且显示为安全链接。 首先需要 SSL证书 。 SSL 证书是跟域名绑定的&#xff0c;还有有效期。 windows 下双击可以查看相关信息。 下载的证书是分 Apache、IIS、Tomcat 和 Nginx 的。 我…

uniapp实现-审批流程效果

一、实现思路 需要要定义一个变量, 记录当前激活的步骤。通过数组的长度来循环数据&#xff0c;如果有就采用3元一次进行选择。 把循环里面的变量【name、status、time】, 全部替换为取出的那一项的值。然后继续下一次循环。 虚拟的数据都是请求来的, 组装为好渲染的格式。 二…

linux中对信号的认识

信号的概念与相关知识认识 信号是向目标进程发送消息通知的的一种机制。 信号可以以异步的方式发送给进程&#xff0c;也就是说&#xff0c;进程无需主动等待&#xff0c;而是在任何时间都可以接收到信号。 信号的种类 用kill-l命令查看系统定义的信号列表&#xff1a; 前台…

thinkphp学习11-数据库的查询表达式

比较查询 查询表达式支持大部分常用的 SQL 语句&#xff0c;语法格式如下 where(字段名,查询表达式,查询条件);在查询数据进行筛选时&#xff0c;我们采用 where()方法&#xff0c;比如 id79&#xff1b; $user1 Db::name(user)->where(id, 79)->find(); $user2 Db::…

巧用二进制实现俄罗斯方块小游戏

效果预览 思想 首先建立两个数组board、tetris用来存储当前已经堆积在棋盘的方块与正在下落的方块。 这两个是一维数组当需要在页面画棋盘时就对其每一项转成二进制&#xff08;看计算属性tetrisBoard&#xff09;&#xff0c;其中1&#xff08;红色&#xff09;0&#xff08;…

加密与安全_深入了解Hmac算法(消息认证码)

文章目录 PreHMAC概述常见的Hmac算法Code随机的key的生成 KeyGeneratorHmacMD5用Hmac算法取代原有的自定义的加盐算法 HmacMD5 VS MD5HmacSHA256 Pre 加密与安全_深入了解哈希算法中我们提到&#xff0c; 存储用户的哈希口令时&#xff0c;要加盐存储&#xff0c;目的就在于抵…

现货黄金价格今日行情怎样把握?

由于受到各种经济和政治因素的影响&#xff0c;国际市场上的黄金价格&#xff0c;每天的行情走势都在不断地波动&#xff0c;有时候行情上涨&#xff0c;有时候行情下跌&#xff0c;如果投资者不懂得灵活地应对&#xff0c;在哪一种行情中都有可能亏损&#xff0c;但如果投资者…

Linux系统CPU模式部署Qwen1.5-14B

Qwen1.5已适配Ollama。 Ollama 是一个命令行聊天机器人&#xff0c;它使得几乎可以在任何地方使用大型语言模型变得简单。 下载 Ollma 安装文件 访问以下网站&#xff1a;https://ollama.com/download/linux 执行&#xff1a;curl -fsSL https://ollama.com/install.sh | sh…

信息安全是什么

信息安全&#xff0c;也称为信息安全或数据安全&#xff0c;是防止未经授权的访问、更改、中断和破坏信息。 信息安全本身包括的范围很大&#xff0c;大到国家军事政治等机密安全&#xff0c;小范围的当然还包括如防范商业企业机密泄露&#xff0c;防范青少年对不良信息的浏览…

解决虚拟机启动报错:“End kernel panic - not syncing: attempted to kill the idle task”

原本能正常运行的虚拟机&#xff0c;很长一段时间没用后&#xff0c;今天再次启动&#xff0c;然后就出现下面的问题&#xff1a; 然后走了一些弯路&#xff0c;比如说删除该虚拟机然后新建一个虚拟机&#xff08;问题未解决&#xff09;、直接删除VitualBox重新安装&#xff0…

探索网络世界:IP代理与爬虫技术的全景解析

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …