非死不可 店面

9.5 的店面 美国小哥 两道题 1. find LCA  假设

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

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

， onsite 加油   

1. def lowest_common_ancestor(root, a, b):
   
2.     ha = height(root, a)
   
3.     hb = height(root, b)
   
4.     while a != b:
   
5.         if ha < hb:
   
6.             b = b.parent
   
7.             hb -= 1
   
8.         elif ha > hb:
   
9.             a = a.parent
   
10.             ha -= 1
    
11.         else:
    
12.             a = a.parent
    
13.             b = b.parent
    
14.             ha -= 1
    
15.             hb -= 1
    
16.     return a  # or b
    
17. 
    
18. 
    
19. def height(root, n):
    
20.     h = 0
    
21.     if not root or not n:
    
22.         return 0
    
23.     while n != root:
    
24.         h += 1
    
25.         n = n.parent
    
26.     return h

复制代码

请问楼主第一题是用hashset解的吗？

谢谢

只有 parents 指针 ？？ 没有right left ??  不可能吧

求详细讲下第一题

第一题 是道面经题， 先判断 a 和 b 哪个离root远， 先移动远的， 当两个再同一层的时候 再同时移动。 现在在外面 我有空写一下

移动 指的是 向上 因为只有 parent 指针

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

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