剑指oferr68-II.二叉树的最近公共祖先

news/2024/5/13 7:43:31/文章来源:https://blog.csdn.net/qq_61009660/article/details/131731525

 为什么这道题的难度是easy,我感觉挺难的啊,我想了挺久没有一点思路就直接看题解了。题解有两种解法,先看第一种存储父节点

class Solution {Map<Integer,TreeNode> parent = new HashMap<Integer,TreeNode>();Set<Integer> visited = new HashSet<Integer>();public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {dfs(root);while(p != null){visited.add(p.val);p = parent.get(p.val);}while(q != null){if(visited.contains(q.val))return q;q = parent.get(q.val);}return null;}private void dfs(TreeNode root){if(root.left != null){parent.put(root.left.val, root);dfs(root.left);}if(root.right != null){parent.put(root.right.val, root);dfs(root.right);}}}

它是用一个parent的HashMap来存储所有节点的父节点,HashMap键值对的类型是<Integer,TreeNode>,Integer是子节点的值,TreeNode是父节点的引用,然后利用parent.get(p.val)的方法获得p的父节点,然后把父节点的值放入一个叫visited的set里面,然后

p = parent.get(p.val),p就变成了他的父节点,在循环一次就把,p的爷爷节点的值放进了set,

对于q而言,就直接看set里面有没有q.val,如果有说明q是p的祖宗,直接返回q就可以,如果没有,q就变成他的父节点,再看set里面有没有,这样一直循环就会找到p和q的最近祖先。

还有一种方法是递归。

class Solution {private TreeNode ans;public Solution(){this.ans = null;}public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {dfs(root, p, q);return this.ans;}private boolean dfs(TreeNode root, TreeNode p, TreeNode q){if(root == null) return false;boolean lson = dfs(root.left, p, q);boolean rson = dfs(root.right, p, q);if((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))){ans = root;}return lson || rson || (root.val == p.val) || (root.val == q.val);}
}

 如果x是p,q的最近公共祖先,那么{x的左子树包含p右子树包含q(左子树包含q右子树包含p)}或者{[x是p x的左子树包含q(右子树包含p)] [x是q x的左子树包含p(x的右子树包含p)]},x只存在大括号这两种情况。因为如果x是最近公共祖先的话,x的一颗子树上不可能同时存在p和q(如果同时存在,那么最近的公共祖先不是x而是x的子孙)这个解释的是第一个大括号,如果x是p的话,那么q一定在x的左子树或者右子树上  解释的是第二个大括号。逻辑搞清楚了,接下来看代码,dfs采用的是左右根的遍历方式。dfs可以看作是自下而上用来标记每个子树是true还是false的方法,如果它的值等于p或q那么他就是true,或者他的左子树或者右子树是true那么他就是true,并且在遍历的同时还会判断这个节点是不是最近公共祖先,判断的方法就是刚才讲的大括号的两种情况,因为是自下而上的,所以最先找到的公共祖先就是最近公共祖先,当找到了这个最近公共祖先后,它也被设置成了true,但是他的兄弟不可能是true,因为pq都在x这边,这样的话对于x的父节点,根据判断条件,flson&&frson是fasle,第二种情况也是false,也就是说x的父节点不可能是最近公共祖先,但是它被标记为了true,但是x的父节点的兄弟不可能是true,因为pq都在x的父节点这边,以此类推可以得出,x的兄弟节点和他的祖先节点都不会变成最近公共祖先。

这个方法逻辑性太强了,我理了半个多小时才把这个逻辑搞清楚,不如方法一容易理解,但是确实很巧妙。

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

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

相关文章

windows nodejs 版本切换

一、按健winR弹出窗口&#xff0c;键盘输入cmd,然后敲回车。然后进入命令控制行窗口&#xff0c;并输入where node查看之前本地安装的node的路径。 二、找到上面找到的路径&#xff0c;将node.exe所在的父目录里面的所有东西都删除。 三、从官网下载安装包 https://github.com/…

Raft算法之日志复制

Raft算法之日志复制 一、日志复制大致流程 在Leader选举过程中&#xff0c;集群最终会选举出一个Leader节点&#xff0c;而集群中剩余的其他节点将会成为Follower节点。Leader节点除了向Follower节点发送心跳消息&#xff0c;还会处理客户端的请求&#xff0c;并将客户端的更…

AP5193 DC-DC宽电压LED降压恒流驱动器 LED电源驱动IC

产品 AP5193是一款PWM工作模式、外围简单、内置功率MOS管&#xff0c;适用于4.5-100V输入的高精度降压LED恒流驱动芯片。电流2.5A。AP5193可实现线性调光和PWM调光&#xff0c;线性调光脚有效电压范围0.55-2.6V.AP5193 工作频率可以通过RT 外部电阻编程来设定&#xff0c;同时…

linux下一个iic驱动(按键+点灯)-互斥

一、前提&#xff1a; 硬件部分&#xff1a; 1. rk3399开发板&#xff0c;其中的某一路iic&#xff0c;这个作为总线的主控制器 2. gd32单片机&#xff0c;其中的某一路iic&#xff0c;从设备。主要是按键上报和灯的亮灭控制。&#xff08;按键大约30个&#xff0c;灯在键的…

day34-servlet 分页

0目录 servlet 1.分页 分页逻辑1&#xff1a;数据库中20条记录&#xff0c;要求每页5条数据&#xff0c;则一共有4页 分页逻辑2&#xff1a;数据库中21条记录&#xff0c;要求每页5条数据&#xff0c;则一共有5页 分页逻辑3&#xff1a;数据库中19条记录&#xff0c;要求每页…

数字 IC 设计职位经典笔/面试题(二)

共100道经典笔试、面试题目&#xff08;文末可全领&#xff09; FPGA 中可以综合实现为 RAM/ROM/CAM 的三种资源及其注意事项&#xff1f; 三种资源&#xff1a;BLOCK RAM&#xff0c;触发器&#xff08;FF&#xff09;&#xff0c;查找表&#xff08;LUT&#xff09;&#xf…

【算法基础】2.1栈和队列(单调栈和单调队列)

文章目录 例题3302. 表达式求值&#xff08;栈的应用&#xff09;&#x1f62d;&#x1f62d;&#x1f62d;&#x1f62d;&#x1f62d;830. 单调栈知识点解法 154. 滑动窗口 &#xff08;单调队列&#xff09;知识点解法 相关链接 & 相关题目 例题 3302. 表达式求值&…

基于weka手工实现多层感知机(BPNet)

一、BP网络 1.1 单层感知机 单层感知机&#xff0c;就是只有一层神经元&#xff0c;它的模型结构如下1&#xff1a; 对于权重 w w w的更新&#xff0c;我们采用如下公式&#xff1a; w i w i Δ w i Δ w i η ( y − y ^ ) x i (1) w_iw_i\Delta w_i \\ \Delta w_i\eta(y…

RabbitMQ 同样的操作一次成功一次失败

RabbitMQ 是一个功能强大的消息队列系统&#xff0c;广泛应用于分布式系统中。然而&#xff0c;我遇到这样的情况&#xff1a;执行同样的操作&#xff0c;一次成功&#xff0c;一次失败。在本篇博文中&#xff0c;我将探讨这个问题的原因&#xff0c;并提供解决方法。 我是在表…

创作一周年纪念日【道阻且长,行则将至】

✨个人主页&#xff1a; 北 海 &#x1f389;所属专栏&#xff1a; 技术之外的往事 &#x1f383;所处时段&#xff1a; 大学生涯[1/2] 文章目录 一、起点一切皆有定数 二、成果尽心、尽力 三、相遇孤举者难起&#xff0c;众行者易趋 四、未来长风破浪会有时&#xff0c;直挂云…

markdown2html 转化流程

定义一个extensions function markedMention() {return {extensions: [{name: mention,level: inline,start(src) {// console.log("markedMention start....", src);return src.indexOf(#)},tokenizer(src, tokens) {const rule /^(#[a-zA-Z0-9])\s?/const match…

JMeter websocket接口测试

前言 在一个网站中&#xff0c;很多数据需要即时更新&#xff0c;比如期货交易类的用户资产。在以前&#xff0c;这种功能的实现一般使用http轮询&#xff0c;即客户端用定时任务每隔一段时间向服务器发送查询请求来获取最新值。这种方式的弊端显而易见&#xff1a; 有可能造…

解决Gson解析json字符串,Integer变为Double类型的问题

直接上代码记录下。我代码里没有Gson包&#xff0c;用的是nacos对Gson的封装&#xff0c;只是包不同&#xff0c;方法都一样 import com.alibaba.nacos.shaded.com.google.common.reflect.TypeToken; import com.alibaba.nacos.shaded.com.google.gson.*;import java.util.Map;…

idea-控制台输出乱码问题

idea-控制台输出乱码问题 现象描述&#xff1a; 今天在进行IDEA开发WEB工程调式的时候控制台日志输出了乱码&#xff0c;如下截图 其实开发者大多都知道乱码是 编码不一致导致的&#xff0c;但是有时候就是不知到哪些地方不一致&#xff0c;今天我碰到的情况可能和你的不相同…

前端框架Layui实现动态表格效果用户管理实例(对表格进行CRUD操作-附源码)

目录 一、前言 1.什么是表格 2.表格的使用范围 二、案例实现 1.案例分析 ①根据需求找到文档源码 ②查询结果在实体中没有该属性 2.dao层编写 ①BaseDao工具类 ②UserDao编写 3.Servlet编写 ①R工具类的介绍 ②Useraction编写 4.jsp页面搭建 ①userManage.jsp ②…

Docker基础——初识Docker

Docker架构 Docker 使用客户端-服务器 (C/S) 架构模式&#xff0c;使用远程API来管理和创建Docker容器。 Docker 客户端(Client) : Docker 客户端通过命令行或者其他工具使用 Docker SDK (https://docs.docker.com/develop/sdk/) 与 Docker 的守护进程通信。Docker 主机(Host…

搭建微服务工程 【详细步骤】

一、准备阶段 &#x1f349; 本篇文章用到的技术栈 mysqlmybatis[mp]springbootspringcloud alibaba 需要用到的数据库 订单数据库: SET NAMES utf8mb4; SET FOREIGN_KEY_CHECKS 0;-- ---------------------------- -- Table structure for shop_order -- --------------…

windows下配置pytorch + yolov8+vscode,并自定义数据进行训练、摄像头实时预测

最近由于工程需要&#xff0c;研究学习了一下windows下如何配置pytorch和yolov8&#xff0c;并自己搜集数据进行训练和预测&#xff0c;预测使用usb摄像头进行实时预测。在此记录一下全过程 一、软件安装和配置 1. vscode安装 windows平台开发python&#xff0c;我采用vscod…

Docker架构

目录 Docker总架构图Docker ClientDocker DaemonDocker ServerDocker EngineJob Docker RegistryGraphDriverGraphDriverNetworkDriverExecDriver LibcontainerDocker Container Docker可以帮助用户在容器内部快速自动化部署应用&#xff0c;并利用Linux内核特性命名空间&#…

uniapp微信小程序使用axios(vue3+axios+ts版)

版本号 "vue": "^3.2.45", "axios": "^1.4.0", "axios-miniprogram-adapter": "^0.3.5", 安装axios及axios适配器&#xff0c;适配小程序 yarn add axios axios-miniprogram-adapter 使用axios 在utils创建utils/…