新鲜狗狗电面

两道挺简单的题：

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

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

昨天面的还没有消息，求一个onsite。顺便求点大米～

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

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

peach_black_tea 发表于 2018-8-30 09:23
时间复杂度是一样的。空间复杂度BFS是O(n), DFS是O(height)。worst case如果tree是linked list的话也是O( ...

tree是linkedlist的话，BFS的空间复杂度是O(1)才对吧？

fanghao 发表于 2018-8-31 00:31
tree是linkedlist的话，BFS的空间复杂度是O(1)才对吧？

后面的worst case只针对DFS。我并没有说linked list的情况是BFS的worst case。

求问楼主
第二题的的一问意思就是遍历tree就node.val的和吗？
follow up可以讲具体一点吗，node组成的数组是怎么样的? 怎么用set解决？

找root是求各个node的in-degree么？in-degree为0即为root。

如果是求tree里面所有node的和，bfs和dfs不是一样的么，时间复杂度的话。空间复杂度是不一样

第二题的follow up不明白，谁能给解释一下？

是不是循环把所有node的子节点都写入set，然后再循环一次，看哪个node不在set里，这个就是root

二院老同志 发表于 2018-8-30 08:25
找root是求各个node的in-degree么？in-degree为0即为root。

嗯是的。我是这么做的。