最新要闻
- 看热讯:小米子公司发通告:拼多多、京东、淘宝上的“紫米官旗”不是我
- 硅谷银行停业没影响!贾跃亭要“翻身”:4月26日FF91终极发布
- 世界今日讯!德国反对2035禁售燃油车!欧盟做出让步:内燃机还有活路
- 天天观热点:Intel要求电源厂商使用单一规格制作12VHPWR接头
- 马斯克减肥神药遭疯抢!欧洲药管局警告:2023年都会短缺
- 宝马iX3高速撞车 车主:车道纠偏系统和自己抢方向盘酿事故
- 环球最新:公司回应因给客户倒水太满开除员工:该走啥程序走啥程序
- 新机型“无可奉告”:任天堂称对Switch未来充满信心
- 【全球速看料】史上最大规模!魅族领克无界生态发布会官宣:魅族20系列、Flyme 10来了
- 全球视点!一加逆袭!成为2023年销量增速最快的品牌:友商普遍下滑
- 共314套房源!昌平区公租房配租公告来了
- 全球视讯!特斯拉叫停与比亚迪合作?比亚迪回应:不实信息
- 环球即时:苹果人事巨震:11位高管扎堆离职 库克也要降薪40%
- 微头条丨燃油车 真凉透了吗
- 【天天时快讯】采用全新NT架构:新Windows端QQ首个版本将于24日发布
- 世界资讯:剧版打破多项纪录!爱奇艺考虑拍《狂飙》电影版 网友评论两级分化
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
天天讯息:剑指 Offer 68 - II. 二叉树的最近公共祖先(java解题)
【资料图】
目录- 1. 题目
- 2. 解题思路
- 3. 数据类型功能函数总结
- 4. java代码
1. 题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 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 为不同节点且均存在于给定的二叉树中。
作者:Krahets链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm/57euni/来源:力扣(LeetCode)著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
2. 解题思路
根据之前二叉搜索树最远公共祖先结点的求解,可以考虑分为root、左子树、右子树三部分来考虑。
- 针对左右子树,分别查找节点
p
、q
位于哪一侧; - 如果两个节点分别位于两侧,可以证明当前
root
节点是最近的公共根节点; - 如果两个节点并不位于两侧,从题目已知两个节点一定在二叉树中,因此可以推断,两个节点位于同一侧;
- 若两节点均位于左侧,则公共根节点一定位于
root
的左子树中,右侧同理 - 之后可考虑使用递归来求解该问题,注意递归的终止条件:
root==null
或者root自身就是p、q之一
。
对于节点p、q位于哪一侧的查找,在算法中使用findNode()
函数进行递归查找。
3. 数据类型功能函数总结
//无
4. java代码
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { //左右子树中查找节点p\q,如果分别位于左右子树,root为公共节点,不然说明两个节点位于同一侧,则直接到某一侧查找 //查找节点——遍历 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==null||root==p||root==q){ return root; } //节点查找 boolean find_p_left=findNode(root.left,p); boolean find_p_right=findNode(root.right,p); boolean find_q_left=findNode(root.left,q); boolean find_q_right=findNode(root.right,q); if((find_p_left&&find_q_right)||(find_p_right&&find_q_left)){ return root; } else{ if(find_p_left){ return lowestCommonAncestor(root.left,p,q); } if(find_p_right){ return lowestCommonAncestor(root.right,p,q); } } return root; } boolean findNode(TreeNode root,TreeNode x){//递归查找节点 if(root==null){ return false; } else if(root ==x){ return true; } else{ return findNode(root.left,x)||findNode(root.right,x); } }}
关键词:
-
天天讯息:剑指 Offer 68 - II. 二叉树的最近公共祖先(java解题)
leetcode《图解数据结构》剑指Offer68-II 二叉树的最近公共祖先(java解题)的解题思路和java代码,并...
来源: 天天讯息:剑指 Offer 68 - II. 二叉树的最近公共祖先(java解题)
分布式架构-可观测性
obs studio 插件
看热讯:小米子公司发通告:拼多多、京东、淘宝上的“紫米官旗”不是我
硅谷银行停业没影响!贾跃亭要“翻身”:4月26日FF91终极发布
世界今日讯!德国反对2035禁售燃油车!欧盟做出让步:内燃机还有活路
天天观热点:Intel要求电源厂商使用单一规格制作12VHPWR接头
马斯克减肥神药遭疯抢!欧洲药管局警告:2023年都会短缺
天天热讯:DockQuery | 基于E-R图的数据建模功能使用实践
宝马iX3高速撞车 车主:车道纠偏系统和自己抢方向盘酿事故
环球最新:公司回应因给客户倒水太满开除员工:该走啥程序走啥程序
新机型“无可奉告”:任天堂称对Switch未来充满信心
【全球速看料】史上最大规模!魅族领克无界生态发布会官宣:魅族20系列、Flyme 10来了
全球视点!一加逆袭!成为2023年销量增速最快的品牌:友商普遍下滑
共314套房源!昌平区公租房配租公告来了
焦点资讯:GO语言学习笔记-测试篇 Study for Go ! Chapter ten- Test
要闻速递:面试官:怎么删除 HashMap 中的重复元素?第 3 种实现思路,99% 的人不会!
世界快消息!k8s的Helm 工具安装
RPC框架JMH测试-chatgpt自动生成
前端设计模式——代理模式
全球视讯!特斯拉叫停与比亚迪合作?比亚迪回应:不实信息
环球即时:苹果人事巨震:11位高管扎堆离职 库克也要降薪40%
微头条丨燃油车 真凉透了吗
【天天时快讯】采用全新NT架构:新Windows端QQ首个版本将于24日发布
世界资讯:剧版打破多项纪录!爱奇艺考虑拍《狂飙》电影版 网友评论两级分化
每日看点!插件化开发详解
关注:读Java性能权威指南(第2版)笔记16_垃圾回收C
全球滚动:京东小程序CI工具实践
巧妙使用SQL Server的计算列实现项目唯一规则快速定制
天天快资讯:免费玩没戏 《暗黑4》不会加入微软XGP:四五百块还是要花的
首位华裔奥斯卡影后!杨紫琼84岁母亲喜极而泣 为女儿感到自豪
世界微资讯!Redis内存碎片深入分析
多举措提高职教吸引力 助力职业教育“强起来”“活起来”
焦点简讯:曝苹果最快2024年商用MicroLED屏:比OLED更香
今日快讯:7月1日普及!我国将全面淘汰传统后视镜 都换汽车电子后视镜:上游供应链已准备好
全球今日报丨老人捡钱不愿归还 女孩崩溃下跪引网友愤怒:律师称可起诉 专家喊话不能仗着年龄大
环球新动态:适合买二手的硬件只有4个:学会省1000元
K8S-Helm
资讯:04-数据类型
环球动态:在Linux中安装containerd作为kubernetes的容器运行时
当前通讯!“自杀式”降价杀红眼:燃油车真凉透了?
乘客出地铁黄鹤楼站的统一姿势:集体反站拍摄绝美夜景
天天动态:大爷充29万做美容反悔起诉退钱:宣称能打通“任督二脉”等
世界聚焦:硅谷银行破产:在营销号那儿 咋又成美国赢了?
从大厂离职后 游戏程序员们过得咋样?
鲍美瑶男朋友大白_鲍美瑶
即时看!第129篇:JS模块化开发
每日快播:Yus框架之nl子级管控指令
鼻炎患者要注意了!今年花粉高峰期来得猛又早:将持续数月
中消协等倡议推广小份菜、半份菜:鼓励线上点餐推出“菜量自动提醒”功能
焦点速读:《流浪地球2》上映51天票房破40亿 豆瓣评分又涨了!导演自曝第三部
AMD技术岗最高头衔!DX10/11发明人、皓龙处理器之父等升任企业院士
22-23(2)第2次线上赛
【打怪升级】【rocketMq】rocket的持久化
Linux进程与线程的基本概念及区别
天天消息!k8s单节点改为高可用和更新证书
世界滚动:这还是中国乒乓球吗?王牌选手接连倒下,对手赢球后开心改签机票
欧盟约法三章:苹果无法对iPhone 15 USB-C加密来限制充电速度
每日快报!董明珠称很烦吹捧她的员工:不敢讲真话 没法信任
环球滚动:高尔夫球“名场面”或消失!剧版《最后生还者2》将修改原作剧情
马来西亚原装进口:猫山王榴莲雪糕4.9元/支四折发车
焦点讯息:联想YOGA Pro系列升级:新机全系标配32GB内存+1TB存储
环球今亮点!清华博士回应送外卖:不是炒作 曾创业欠下了百万元债务
环球今热点:299元 雷神X3电竞路由器上架:512MB内存 可253台设备同时连
即时看!比亚迪又拿大单:英国公司订购5000辆元Plus EV 价格比国内贵了一倍
全球热点!最强消费级PCIe 5.0 SSD有多强!技嘉大雕510K 2TB评测:顺序读写破10GB/s、4K超100MB/s
全球速讯:使用symbolicatecrash工具符号化Crash日志
环球速看:开心档之HTML 属性
全球热门:博雅互动(00434.HK)将于3月23日举行董事会会议以审批全年业绩
世界消息!官方:着力解决自媒体内容失真问题、清除违规吸粉
董明珠称批评人很快乐:帮助对方成长
不受支持的PC强行升级Win11 烦人的水印又回来了 微软回应
快看:PPT既视感!电视剧《狂飙》更换新片头:曾被指抄袭网飞纪录片
天天最资讯丨哈佛大学研究:体力劳动更多的男性生育能力更强
当前热点-网站https 问题记录
出道即封神的ChatGPT,现在怎么样了?
IntelliJ IDEA使用教程——不使用maven管理下导入jar包
每日精选:使用Docker搭建MinIO集群服务
CommonsBeanUtils1反序列化分析
全球快资讯:董明珠:如果员工经常在我面前拍马屁 我就开除他
当前关注:网店因商品拆封拒绝七天无理由退货:最终被罚4万元
焦点!全村停电 男子用比亚迪DM-i给自家全屋供电 邻居:为啥就他家有电?
丫丫伙食新添胡萝卜:但它没碰
天天快讯:剧版《最后生还者》顺利收官:M站评分达84分
CommonsCollections4反序列化分析
环球视讯!前端开发爬虫首选puppeteer
聚焦:subtotal函数的作用_SUBTOTAL函数的用法
环球观天下!中国移动涨停 市值2.1万亿创历史新高 挑战A股第一贵州茅台
今日聚焦!亲肤0刺激 润本婴儿驱蚊喷雾大瓶9.9(超市39.9)
天天视讯!高蛋白低脂美味!舌里减脂鸡胸肉5袋到手12.9元
头条焦点:净利润翻倍 宁德时代在补什么课?
最新资讯:卖事故车被判退一赔三!车主:特斯拉让我赔代步车50万租金
环球消息!【数字化运营】PagerDuty平台与上海道宁帮助您的数字基础设施中自动化、编排和加速响应
LocalDateTime应用比较日期
玩家不用担心 分析师称微软收购动视暴雪只会伤害索尼
全球观焦点:游客吐槽25元看海洋馆就几个鱼缸:现场和家里客厅一样大
环球百事通!樱桃推出KW 9200 MINI超薄键盘:剪刀脚按键、三模连接
全球快资讯丨雅阁车主第一次坐比亚迪汉 自侃像是土包子进城 信仰崩塌
焦点讯息:美国公示丫丫回国相关申请:快回家了!
全球观速讯丨二进制安全——缓冲区溢出