fb summer intern second round

打开了才知道FB的电话面试是带视频的～不要忘了化妆

题目：
Given a tr

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

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

ntime O(n), space O(1)

实际上是力扣160

Kaixuan 发表于 2019/10/07 09:59:33
楼主可以的，加油

你是不是有毒哈哈哈哈哈哈

先计算A，B的depth，如果depth不同的话需要把A或者B的ref向上移动abs{depth(A) - depth(B)}，这时两个ref就在同一个level上了，然后两个ref再一起向上移动，碰到的第一个相同node就是LCA，这样可以吧？

请问楼主就一道题吗？是普通的lca吗

carldream120 发表于 2019/10/06 00:28:55
请问楼主就一道题吗？是普通的lca吗

是的…太扎心了…因为我太菜了所以只有一道题

请问LZ投的是什么岗位呀

Delia_dd 发表于 2019-10-6 00:45
请问LZ投的是什么岗位呀

SDE summer intern

请问是不是应该用hashmap建立parent和children的关系 然后用hashset遍历的时候记录， 如果有重复的node就返回呀（题目里是只有parent node吗 还有left和right node吧？）

carldream120 发表于 2019/10/06 01:02:21
请问是不是应该用hashmap建立parent和children的关系 然后用hashset遍历的时候记录， 如果有重复的node就返回呀（题目里是只有parent node吗 还有left和righ...

space 要求O（1） 只有parent没有left or right

bonniezhou0515 发表于 2019-10-6 01:03
space 要求O（1） 只有parent没有left or right

哦哦 那请问有什么好的方法吗 只想出来用hashset的方法。。

有意思，披了lca马甲的求两链表交点的题

先从一个node向上遍历，遍历的过程中把parent设为None，再遍历第二个node，一旦发现某个node没有parent，这个node就是lca。但是这样会破坏数据结构。不知道有木有更好的方法