当前位置: 首页 > news >正文

算法题--二叉树(二叉树的最近公共祖先、重建二叉树、二叉搜索树的后序遍历序列)

目录

二叉树

题目

二叉树的最近公共祖先

原题链接

解析

二叉搜索树的最近公共节点

核心思想

答案

重建二叉树

题目链接

解析

核心思想

答案

二叉搜索树的后序遍历序列

原题链接

解析

核心思想

答案


二叉树

该类题目的解决一般是通过节点的遍历去实现,一般是分两种。

一是递归(深度优先),该方法通常代码比较简单,难懂。首先需要确定入参和返回的内容,然后确定层级之间的关系,最后去找递归的出口。

二是广度优先(该方法一般只有可以分层次处理的才能用),该方法代码量多,易懂。首先借助数组存储第一层的节点,然后每次将数组中的节点分批从数组头部取出(当对比2个节点时就一次取2个),处理完后将对应的子节点分批再从数组尾部存入数组(注意需要对比的子节点相邻存入,这样取出正好配对)。递归上述步骤直到数组为空。
注意特殊的二叉树会满足一些条件。

题目

二叉树的最近公共祖先

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

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

例如,给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]

示例 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。因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉树中。
/*** Definition for a binary tree node.* function TreeNode(val) {*     this.val = val;*     this.left = this.right = null;* }*/
var lowestCommonAncestor = function(root, p, q) {};

原题链接

力扣

解析

注意一些树的节点之间会有大小关系,更方便于解题,例如二叉搜索树,二叉搜索树的左节点(包括其子节点上的值)小于根节点,右节点(包括其子节点上的值)大于根节点。

例如类似题目

二叉搜索树的最近公共节点

力扣

核心思想

方法一(递归)

1.确定入参和出参,入参:1需要检索当前节点root,2需要检索当前的节点下是否有目标节点p、q;出参:返回的目标节点或最近公共节点。

2.确定上下层关系,当root的左右两边节点出现p和q时,当前节点为公共的父节点。当只有一个左右节点中只有一个节点为目标节点时,返回目标节点。

3.找出口,当root不存在、或者root为目标节点时,返回root。

方法二(广度优先+哈希表存储父节点):

1.首先用广度优先算法遍历每个接地那,构建一个哈希表存储子节点对应父节点的关系。

2.求出p的所有父节点放入集合中。

3.从q节点往上取所有父节点,直到有父节点在p的父节点集合中存在。

答案

方法一(递归)

var lowestCommonAncestor = function (root, p, q) {if (!root || root === p || root === q) return root;const left = lowestCommonAncestor(root.left, p, q);const right = lowestCommonAncestor(root.right, p, q);if(left && right){return root}else{return left||right}
};

方法二(广度优先+哈希表存储父节点)

var lowestCommonAncestor = function(root, p, q) {let queue = [root],parent = new Map();while(queue.length && (!parent.has(p) || !parent.has(q))){const node = queue.shift();node.left && queue.push(node.left);node.right && queue.push(node.right);node.left && parent.set(node.left, node);node.right && parent.set(node.right,node);}let pSet = new Set(),node = p;pSet.add(node);while(parent.has(node)){pSet.add(parent.get(node));node = parent.get(node);}node = q;if(pSet.has(node)) return node;while(parent.has(node)){node = parent.get(node);if(pSet.has(node)) return node;}return null;    
};

重建二叉树
 

输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]
/*** Definition for a binary tree node.* function TreeNode(val) {*     this.val = val;*     this.left = this.right = null;* }*/
var buildTree = function(preorder, inorder) {};

题目链接

力扣

解析

前序遍历的顺序是根左右,中序遍历的顺序为左根右。

以示例1解释,[3,9,20,15,7]前序遍历的第一个值3一定为根的值,我们将它取出,前序遍历剩余[9,20,15,7]。
3在中序遍历[9,3,15,20,7]中的位置,可以分割出[9],[15,20,7],我们知道[9]一定是根3的左子树的中序遍历,[15,20,7]一定是根3的右子树的中序遍历。

核心思想

递归

1.确定入参和出参,入参:前序遍历的后续遍历的序列。出参:根据遍历返回的当前根节点。

2.确定上下层关系,每次根据前序找到根节点,根据根节点在中序中划分属于左右节点的部分。

f(p,q)={ val:xxx,left:f(pl,ql),right:f(pr,qr)}。

3.找出口,当preorder不存在时。

答案

递归

var buildTree = function(preorder, inorder) {if (!preorder.length) {return;}const val = preorder.shift()const index = inorder.findIndex(item => item === val)const left = inorder.slice(0, index)const right = inorder.slice(index + 1)return {val,left: buildTree(preorder.slice(0, index), left),right: buildTree(preorder.slice(index), right)}
};

二叉搜索树的后序遍历序列

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树:

     5/ \2   6/ \1   3

示例 1:

输入: [1,6,3,2,5]
输出: false

示例 2:

输入: [1,3,2,6,5]
输出: true
/*** @param {number[]} postorder* @return {boolean}*/
var verifyPostorder = function(postorder) {};

原题链接

力扣

解析

二叉搜索树的左节点(包括其子节点上的值)小于根节点,右节点(包括其子节点上的值)大于根节点。故二叉搜索树可以只根据一个顺序的序列结果就可以构造树。

核心思想

递归

1.确定入参和出参,入参:当前序列。

2.确定上下层关系,取序列最后一个节点为根节点,每次根据当前序列,找到第一个大于根节点的,该元素的左边应该全部小于根节点,右边应该全部大于根节点,满足的话对左右两边的序列进行递归,f(x)=f(x.left)&&f(x.right)。

3.找出口,当preorder不存在时结束。

答案

递归

var verifyPostorder = function(postorder) {if (postorder.length <= 2) {return true}const root = postorder.pop()let index = postorder.findIndex(num => num > root)index = index === -1 ? postorder.length : indexconst left = postorder.slice(0, index)const right = postorder.slice(index)if(!(left.every(num => num < root) && right.every(num => num > root))){return false}return  verifyPostorder(left) && verifyPostorder(right)
};

相关文章:

算法题--二叉树(二叉树的最近公共祖先、重建二叉树、二叉搜索树的后序遍历序列)

目录 二叉树 题目 二叉树的最近公共祖先 原题链接 解析 二叉搜索树的最近公共节点 核心思想 答案 重建二叉树 题目链接 解析 核心思想 答案 二叉搜索树的后序遍历序列 原题链接 解析 核心思想 答案 二叉树 该类题目的解决一般是通过节点的遍历去实现&#x…...

mysql的基础面经-索引、事务

1 聚簇索引 1 和主键索引的关系 2 和非聚簇索引的关系&#xff0c;其叶子节点存储的是聚簇索引中的主键 3 索引覆盖机制使得非聚簇索引不用回表二次查询 2 举一个使用索引覆盖的例子 我的项目中没有使用到覆盖索引&#xff0c;但是可以举一个例子&#xff0c;比如我直接为年…...

Windows下双网卡配置静态路由,实现内外网同时使用

怎么样设置双网卡&#xff1f;内网外网两个网络这么同时连接&#xff1f; 接下来听好了&#xff0c;赶紧动手 情况描述&#xff1a; 我使用的Windows10电脑&#xff0c;支持双网卡工作 目前我工作需要使用的使用内网&#xff0c;但是又需要使用外网&#xff0c;需要同时使用&a…...

Spring整合Mybatis、Spring整合JUnit

&#x1f40c;个人主页&#xff1a; &#x1f40c; 叶落闲庭 &#x1f4a8;我的专栏&#xff1a;&#x1f4a8; c语言 数据结构 javaweb 石可破也&#xff0c;而不可夺坚&#xff1b;丹可磨也&#xff0c;而不可夺赤。 Spring整合 一、Spring整合Mybatis1.1 整合Mybatis&#x…...

Devops系统中jira平台迁移

需求:把aws中的devops系统迁移到华为云中,其中主要是jira系统中的数据迁移,主要方法为在华为云中建立一套 与aws相同的devops平台,再把数据库和文件系统中的数据迁移,最后进行测试。 主要涉及到的服务集群CCE、数据库mysql、弹性文件服务SFS、数据复制DRS、弹性负载均衡ELB。 迁…...

【雕爷学编程】MicroPython动手做(29)——物联网之SIoT

知识点&#xff1a;什么是掌控板&#xff1f; 掌控板是一块普及STEAM创客教育、人工智能教育、机器人编程教育的开源智能硬件。它集成ESP-32高性能双核芯片&#xff0c;支持WiFi和蓝牙双模通信&#xff0c;可作为物联网节点&#xff0c;实现物联网应用。同时掌控板上集成了OLED…...

LAXCUS分布式操作系统引领科技潮流,进入百度首页

信息源自某家网络平台&#xff0c;以下原样摘抄贴出。 随着科技的飞速发展&#xff0c;分布式操作系统做为通用基础平台&#xff0c;为大数据、高性能计算、人工智能提供了强大的数据和算力支持&#xff0c;已经成为了当今计算机领域的研究热点。近日&#xff0c;一款名为LAXCU…...

Linux--按行读取数据:fgets

函数定义&#xff1a; char *fgets(char *s,int size,FILE *stream); S是指接受数据缓冲区&#xff0c;用于存放stream里读取的数据 size是指缓冲区的大小 返回值为NULL表明读取失败&#xff0c;反之读取成功...

express学习笔记5 - 自定义路由异常处理中间件

修改router/index.js&#xff0c;添加异常处理中间件 *** 自定义路由异常处理中间件* 注意两点&#xff1a;* 第一&#xff0c;方法的参数不能减少* 第二&#xff0c;方法的必须放在路由最后*/ router.use((err, req, res, next) > {console.log(err);const msg (err &…...

filebeat介绍

1、filebeat概述 Filebeat是用于转发和集中日志数据的轻量级传送工具。Filebeat监视您指定的日志文件或位置&#xff0c;收集日志事件&#xff0c;并将它们转发到Elasticsearch或 Logstash或kafka进行索引 1.1 Filebeat两个主要组件 prospector 和 harvester。 prospector&a…...

使用SSM框架实现个人博客管理平台以及实现Web自动化测试

文章目录 前言1. 项目概述2. 项目需求2.1功能需求2.2 其他需求2.3 系统功能模块图 3. 开发环境4. 项目结构5. 部分功能介绍5.1 数据库密码密文存储5.2 统一数据格式返回5.3 登录拦截器 6. 项目展示7. 项目测试7.1 测试用例7.2 执行部分自动化测试用例 前言 在几个月前实现了一…...

【深度学习】MAT: Mask-Aware Transformer for Large Hole Image Inpainting

论文&#xff1a;https://arxiv.org/abs/2203.15270 代码&#xff1a;https://github.com/fenglinglwb/MAT 文章目录 AbstractIntroductionRelated WorkMethod总体架构卷积头Transformer主体Adjusted Transformer Block Multi-Head Contextual Attention Style Manipulation Mo…...

PyTorch BatchNorm2d详解

通常和卷积层&#xff0c;激活函数一起使用...

慕课网Go-4.package、单元测试、并发编程

package 1_1_User.go package usertype User struct {Name string }1_1_UserGet.go package userfunc GetCourse(c User) string {return c.Name }1_1_UserMain.go package mainimport ("fmt"Userch03 "goproj/IMOOC/ch03/user"//别名&#xff0c;防止同名…...

[JavaWeb]SQL介绍-DDL-DML

SQL介绍-DDL-DML 一.SQL简介1.简介2.SQL通用语法3.SQL语言的分类 二.DDL-操作数据库与表1.DDL操作数据库2.DDL操作表①.查询表(Retrieve)②.创建表(Create)③.修改表(Update)④.删除表(Delete) 三.Navicat的安装与使用四.DML-操作表数据1.添加(Insert)2.修改(Update)3.删除(Del…...

git源码安装(无sudo权限)

git源码安装&#xff08;无sudo权限&#xff09; 下载源码解压安装添加到环境变量 下载源码 去https://mirrors.edge.kernel.org/pub/software/scm/git/下载需要的版本。我下载的是2.41.0版本 wget https://mirrors.edge.kernel.org/pub/software/scm/git/git-2.41.0.tar.gz解…...

Web3 叙述交易所授权置换概念 编写transferFrom与approve函数

前文 Web3带着大家根据ERC-20文档编写自己的第一个代币solidity智能合约 中 我们通过ERC-20一种开发者设计的不成文规定 也将我们的代币开发的很像个样子了 我们打开 ERC-20文档 我们transfer后面的函数就是transferFrom 这个也是 一个账号 from 发送给另一个账号 to 数量 val…...

Redis系列二:Clion+MAC+Redis环境搭建

1. ClionMACRedis-3.0-annotated环境搭建 参考&#xff1a; https://github.com/huangz1990/redis-3.0-annotated https://gitee.com/dumpcao/redis-3.0-annotated-cmake-in-clion https://tool.4xseo.com/a/12910.html 1.1 下载并导入Clion git clone https://gitee.com/dum…...

Linux下 Docker容器引擎基础(2)

目录 创建私有仓库 将修改过的nginx镜像做标记封装&#xff0c;准备上传到私有仓库 将镜像上传到私有仓库 从私有仓库中下载镜像到本地 CPU使用率 CPU共享比例 CPU周期限制 CPU 配额控制参数的混合案例 内存限制 Block IO 的限制 限制bps 和iops 创建私有仓库 仓库&a…...

现场服务管理系统有哪些?5个现场服务管理软件对比

现场售后服务管理软件的使用者通常是机械设备、家电、仪表仪器、医疗器械等厂商的工程师和客服调度人员。现场售后服务管理软件可将服务过程标准化&#xff0c;包括工单派发、服务过程步骤、配件订购出货和付款、客户评价都有系统支持&#xff0c;有的现场售后服务软件还支持数…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...