狗家店面

share一下昨天狗家店面。面试官国人小哥，出了一道很简单的题（感谢感谢，祝工作顺利！！），而且一直在给hint。全程不到四十分钟吧，讲题+做题时间也就三十分钟。

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

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

这道题好像lc上做过，但是找不到是哪道题了。。。知道的同学求告诉一下。

SaltSprayAir 发表于 2018-9-7 04:00
LZ的朋友来补充：题目不给root节点，node有parent属性

那就一路找回去，两边各一步，记录访问到的node，如果有重复，说明到lca了，再跑一遍计算步数就好了

可以转换成graph 然后bfs吗？

limpalong 发表于 2018-9-3 01:44
这题好像是脸家的面筋题，找出两个node各自的深度，再找出他们lca的深度，然后各自深度相加-2*lca深度

昂为什么要这样做。直接从两个node网上找到lca，中途记录下走了多少步不就可以了吗

吴撕散？
只是最长变成了最短？

可能类似863. All Nodes Distance K in Binary Tree ，但这个是给距离求node的。第一反应是BFS吧……
ls的543是「任意两个点距离最大」，而这里问的是「给定两个点求(最短)距离」……

ruolan_cmu 发表于 2018-9-1 01:53
吴撕散？
只是最长变成了最短？

如果是Tree的话如果不重复不是只有唯一的一条path么，不分最长最短吧

szyyn95 发表于 2018-9-1 01:58
如果是Tree的话如果不重复不是只有唯一的一条path么，不分最长最短吧

嗷嗷不好意思没仔细看

先找最近的共同祖先 再从共同祖先分别求距离如何呢

auronoda 发表于 2018-9-1 13:25
先找最近的共同祖先 再从共同祖先分别求距离如何呢

嗯嗯这个就是我的做法。

请问楼主出结果了吗？

sugarc 发表于 2018-9-2 04:21
请问楼主出结果了吗？

还没有 紫薯紫薯

这题好像是脸家的面筋题，找出两个node各自的深度，再找出他们lca的深度，然后各自深度相加-2*lca深度