F的一道面试题求解

看到FB的一题，Lowest common

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

t;2)应该怎么做？

两个node不在BT里，那也只是跑一遍发现没有结果。多个子节点我不清楚你是指由duplicate还是找多个distinct value节点的LCA，前者的话只能整个树的所有subtree跑一遍不断更新，后者就是找两点的LCA与另一点的LCA再与另一点的LCA etc

我的假设是不管哪种tree都只问两个点的ancestor，即使是multi-tree也是

所以，
自己create一个struct，里面存那两个点有没有找到以及假如都找到了它们相对应的ancestor

每次只要自己跟他的左右(或children)做比较就好

Lintcode有BT版的题目，一模一样，你可以去做做看

无量塔 发表于 2017-9-24 04:03
两个node不在BT里，那也只是跑一遍发现没有结果。多个子节点我不清楚你是指由duplicate还是找多个distinct  ...

谢谢思路啊

chris612ku 发表于 2017-9-24 04:16
我的假设是不管哪种tree都只问两个点的ancestor，即使是multi-tree也是

所以，

好的，多谢提醒，我等会去看一下

1. o(n) 遍历一遍整个树，看看两个nodes都在不在。确定都在了，然后用正常的方式处理。2. search 完每个subtree后多返回关于有没有找到node的一个flag。cc189里面有详解。

Jazzouple.Lee 发表于 2017-9-24 12:51
1. o(n) 遍历一遍整个树，看看两个nodes都在不在。确定都在了，然后用正常的方式处理。2. search 完每个sub ...

看来还是自己准备的不够，大家都熟记于心，谢谢你的提醒，我马上去看看。

Sendoh2015 发表于 2017-9-24 12:53
看来还是自己准备的不够，大家都熟记于心，谢谢你的提醒，我马上去看看。

楼主加油