一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1049|回复: 19
收起左侧

[算法题] 找一个二叉树上某两个节点的共同祖先,不得使用额外的数据结构,二叉树不一定是BST

[复制链接] |试试Instant~ |关注本帖
MTC 发表于 2014-10-19 20:21:54 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
这题店面是不是有些难?
chopper 发表于 2014-10-19 21:48:24 | 显示全部楼层
本帖最后由 chopper 于 2014-10-19 21:49 编辑

如果这2个点存在在树上,直接得到他们的位置,再dep--算出共同根就行了。
如果有多次请求,可以用二进制加速。PS:如果只考第1问,算一般的题。
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2014-10-19 21:49:22 | 显示全部楼层
初初的想法,先通过parent, parent....找到他们所在的层数。然后就大家一起往上。比如说一个在5层,一个在4层。那么5层的找一下Parent,那个Parent在4层。看看和4层的比较是不是一样。如果不一样,则找到大家的3层的Parent,比较是不是一样。这么顺下去。不一定是最优的。。。
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-10-19 21:54:16 | 显示全部楼层
  1.   public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
  2.     if (root == null) return null;   
  3.     if (root == node1 || root == node2) return root;
  4.    
  5.     TreeNode left_result = lowestCommonAncestor(root.left, node1, node2);
  6.     TreeNode right_result = lowestCommonAncestor(root.right, node1, node2);

  7.     if (left_result != null && right_result != null) return root;
  8.     else if (left_result == null && right_result != null) return right_result;
  9.     else return left_result;
  10.   }
复制代码
回复 支持 反对

使用道具 举报

flyaway25 发表于 2014-10-19 22:05:38 | 显示全部楼层
这不是cc上面的原题么?关键就是判断两个目标点在当前点的情况下是否在左右两个子树上面,如果是则返回当前点,否则就是在同一侧然后继续traverse这一侧。
回复 支持 反对

使用道具 举报

fate7612 发表于 2014-10-19 23:55:50 | 显示全部楼层

感觉有点小问题,就是如果一个node正好是另一个node的ancestor,上面的程序会报错。当然就是在这个程序上稍微加点判断条件就好了~
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-10-20 00:03:49 | 显示全部楼层
fate7612 发表于 2014-10-19 10:55
感觉有点小问题,就是如果一个node正好是另一个node的ancestor,上面的程序会报错。当然就是在这个程序上 ...

哪里会报错?
回复 支持 反对

使用道具 举报

jackjiang2 发表于 2014-10-20 03:19:05 | 显示全部楼层
本帖最后由 jackjiang2 于 2014-10-19 14:20 编辑

不难吧 如果给了parent属性还好
回复 支持 反对

使用道具 举报

jackjiang2 发表于 2014-10-20 03:19:36 | 显示全部楼层
jackjiang2 发表于 2014-10-19 14:19
不难 直接 二叉树的非递归后序遍历 找出这两个节点 比较此时栈内的数值

奥 没看出来不用其他数据结构
回复 支持 反对

使用道具 举报

bjik 发表于 2014-10-20 08:18:45 | 显示全部楼层

node1是node2的parent的时候 会有问题吧?
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-10-20 09:12:11 | 显示全部楼层
bjik 发表于 2014-10-19 19:18
node1是node2的parent的时候 会有问题吧?

什么问题你倒是说啊?
回复 支持 反对

使用道具 举报

bjik 发表于 2014-10-20 09:22:03 | 显示全部楼层
本帖最后由 bjik 于 2014-10-20 09:35 编辑

又看了一下 应该是如果一个node不在这个tree里的话 你的程序依然会return另一个node
回复 支持 反对

使用道具 举报

bjik 发表于 2014-10-20 09:36:17 | 显示全部楼层
北美农民 发表于 2014-10-20 09:12
什么问题你倒是说啊?

忘了点回复
回复 支持 反对

使用道具 举报

readman 发表于 2014-10-20 09:57:35 | 显示全部楼层

这题要是全部角落case都想出来 可长了..
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-10-20 10:08:16 | 显示全部楼层
bjik 发表于 2014-10-19 20:22
又看了一下 应该是如果一个node不在这个tree里的话 你的程序依然会return另一个node

这完全看你怎么调用..

如果我加一个dummy root就不会.
回复 支持 反对

使用道具 举报

bjik 发表于 2014-10-20 10:26:51 | 显示全部楼层
北美农民 发表于 2014-10-20 10:08
这完全看你怎么调用..

如果我加一个dummy root就不会.

dummy root怎么解决一个node不在这个tree里的问题啊  请指教
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-10-20 10:30:36 | 显示全部楼层
bjik 发表于 2014-10-19 21:26
dummy root怎么解决一个node不在这个tree里的问题啊  请指教

就在原root上加一个dummy做parent.
回复 支持 反对

使用道具 举报

 楼主| MTC 发表于 2014-10-20 12:42:31 | 显示全部楼层
北美农民 发表于 2014-10-20 10:30
就在原root上加一个dummy做parent.

不給添加
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-10-20 12:44:47 | 显示全部楼层

只需要我调用的时候添加就是了。 原数据结构不用变。
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-10-20 12:45:05 | 显示全部楼层

只需要我调用的时候添加就是了。 原数据结构不用变。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 14:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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