查看: 1678|回复: 0

[转载] Lintcode88 Lowest Common Ancestor solution 题解

[复制链接]
论坛徽章:
0
发表于 2017-12-23 21:50 | 显示全部楼层 |阅读模式
【题目描述】


Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.
The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.
给定一棵二叉树,找到两个节点的最近公共父节点(LCA)。
最近公共祖先是两个节点的公共的祖先节点且具有最大深度。
【注】假设给出的两个节点都在树中存在
【题目链接】
www.lintcode.com/en/problem/lowest-common-ancestor/
【题目解析】
可以用递归来解决,递归寻找两个带查询LCA的节点p和q,当找到后,返回给它们的父亲。如果某个节点的左右子树分别包括这两个节点,那么这个节点必然是所求的解,返回该节点。否则,返回左或者右子树(哪个包含p或者q的就返回哪个)。
【参考答案】
www.jiuzhang.com/solutions/lowest-common-ancestor/



作者:程风破浪会有时
链接:https://www.jianshu.com/p/88ff771aeaaa
來源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

DTCC2020中国数据库技术大会 限时8.5折

【架构革新 高效可控】2020年6月4日~6日第十一届中国数据库技术大会将在北京隆重召开。

大会设置2大主会场,20+技术专场,将邀请超百位行业专家,重点围绕数据架构、AI与大数据、传统企业数据库实践和国产开源数据库等内容展开分享和探讨,为广大数据领域从业人士提供一场年度盛会和交流平台。

http://dtcc.it168.com


大会官网>>
TOP技术积分榜 社区积分榜 徽章 团队 统计 知识索引树 积分竞拍 文本模式 帮助
  ITPUB首页 | ITPUB论坛 | 数据库技术 | 企业信息化 | 开发技术 | 微软技术 | 软件工程与项目管理 | IBM技术园地 | 行业纵向讨论 | IT招聘 | IT文档
  ChinaUnix | ChinaUnix博客 | ChinaUnix论坛
CopyRight 1999-2011 itpub.net All Right Reserved. 北京盛拓优讯信息技术有限公司版权所有 联系我们 
京ICP备09055130号-4  北京市公安局海淀分局网监中心备案编号:11010802021510 广播电视节目制作经营许可证:编号(京)字第1149号
  
快速回复 返回顶部 返回列表