领英店面

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

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

谢谢楼主分享

匿名用户 发表于 2022-01-05 06:22:23
第二小我是用一个变量去不停更新，第三小就是再加一个变量，两个变量同时更新

那样就相当于遍历所有然后通过比较记下第三小喽？这样是不是没用到tree的特性呀

匿名者 发表于 2022-1-5 06:22
看一下我给楼上的回复哈

大概这样
两个全局变量更新，找到第二小之后还有 继续递归找第三小，然后当前值是第一小或者第二小都继续递归，直到找到第三小

1. class Solution:
   
2.     def findSecondMinimumValue(self, root):
   
3.         self.min2 = float('inf')
   
4.         self.min3 = float('inf')
   
5.         min1 = root.val
   
6. 
   
7.         def dfs(node):
   
8.             if not node: return
   
9.             if min1 < node.val < self.min2:
   
10.                 self.min2 = node.val
    
11.                 dfs(node.left)
    
12.                 dfs(node.right)
    
13.             elif node.val > self.min2 > min1:
    
14.                 self.min3 = node.val
    
15.             elif node.val == min1 or node.val == self.min2:
    
16.                 dfs(node.left)
    
17.                 dfs(node.right)
    
18. 
    
19.         dfs(root)
    
20.         return self.min3 if self.min3 < float('inf') else -1

复制代码

jhdyss 发表于 2022-01-05 09:52:07
那样就相当于遍历所有然后通过比较记下第三小喽？这样是不是没用到tree的特性呀

遍历的时候当然要考虑特性剪枝呀，这和用两个变量去更新无关吧

jhdyss 发表于 2022-01-04 21:34:19
求问下第二题的followup怎么搞呢，bfs走一遍吗

可能遍历这个词误导了sorry，我用的dfs，然后剪枝，有个回复贴了代码你可以参考看看

可以问一下lz第一问的binary search咋做的吗？感觉如果是找第一个true，mid只有是true的时候才能说只考虑左半部分，如果是false，第一个true在两边都有可能呀？求思路～万分感谢！！

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

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

第一题的followup没怎么明白 如果用binary search的话题目应该问的不是最多能place多少吧？不然还是需要遍历所有的 毕竟二分每次会砍掉一半

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

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