找回密码
 立即注册

本文来自

电脑/上网

电脑/上网

订阅|关注

致力于提供软件新闻发布,和软件知识学习,包括常用软件应用技巧及评测,创意设计相关的图文及视频教程

面试题50. 树中两个结点的最低公共祖先结点

[复制链接]
380 deltaliu 发表于 2017-9-13 17:24:53
给出一个二叉树,找到两个结点的最低公共祖先。比如下面的二叉树中,5和1的最低公共祖先就是3;
4和6的最低公共祖先就是5。
_______3______
___5__ ___1__
/ \ / \
6 _2 0 8
7 4
思路:
如果p在左子树里,q在右子树里(或者反过来,p在右子树,q在左子树),说明当前节点为pq的最小祖先。
反之,说明pq要么都在左子树里,要么都在右子树里。需要分别遍历左子树和右子树。
用后续遍历的思想,从下往上,如果遇到了p(或q),就把p(或q)的值向上返回。以下图为例,p=3,q=9。现在要查找3和9的最近祖先。把3和9一层一层向上返回,直到6。此时6的左子树接收返回值3,右子树接收返回值9,说明6是3和9的最近祖先。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) {
return root;
TreeNode left = lowestCommonAncestor(root.left, p, q); // 从root.left找p、q
TreeNode right = lowestCommonAncestor(root.right, p, q); // 从root.right找p、q
//if(left != null right != null) return root;
// 替换成下面的语句也可以
if((left == p right == q)||(left == q right == p)) {
return root;
return (left != null) ? left : right;
参考:http://blog.csdn.net/u010429424/article/details/77650420

面试题:8个试剂,其中一个有毒,最少多少只小白鼠能检测出有毒试剂
u010429424:
@localhostlucky123:对的,就是最近在求职,看到这个笔试题经常考。平时是不会纠结这个...

面试题:8个试剂,其中一个有毒,最少多少只小白鼠能检测出有毒试剂
qq_18674097:
8个试剂其中一个有毒 ,为什么要这么复杂?? 直接就一直小白鼠就可以了啊,吃了哪瓶死了就说明哪瓶有毒...

面试题:8个试剂,其中一个有毒,最少多少只小白鼠能检测出有毒试剂
zmq2817:
在方法一的基础上再加两只。先三只吃完,如果两只死或者三只死或者三只活,结果不变。如果有两只不死,例如...

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
温馨提示:
1、在论坛里发表的文章仅代表作者本人的观点,与本网站立场无关。
2、论坛的所有内容都不保证其准确性,有效性,时间性。阅读本站内容因误导等因素而造成的损失本站不承担连带责任。
3、若因线路及非本站所能控制范围的故障导致暂停服务期间造成的一切不便与损失,论坛不负任何责任。
4,本网站内容均摘自其他网站,如涉及侵权定当第一时间删除
5、如侵犯您的权益请联系936144721@qq.com



上一篇:街头拉丁是什么鬼!跳拉丁的就是要不走寻常路~
下一篇:糖水豆花的做法,糖水豆花怎么做好吃,糖水豆花的家常
转载请说明出处,本文地址:http://bbs.imicun.com/thread-15463858-1-1.html
回复

使用道具 举报

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

本版积分规则

快速回复 返回顶部 返回列表