Google MTV 全套过经

楼主第二题怎么做的？先把每个id留下最小的m个在再找k个最小的吗？

楼主想问一下 第二题 是直接按照val sort 一遍直接for 循环pick吗
还有就是第五题，能不能直接保存一个全局变量sum，每次 root.left is None and root.right is None的时候add一下
另外想问一下楼主能否细节的说一下  next  和parent这个做法是什么样的， 感觉好像做不到lgn。。

第一题懵逼啊。。 楼主能详细讲讲么？

第五轮为什么需要next and parent pointer? 不是比较简单的题目么？dfs遍历所有节点，只要判断没有child就是leaf,把value加到sum. 求楼主指出我哪里想错了

Macrame 发表于 2018-12-1 14:42
这个题目是近期的面试高频题目吧，用union-find做
关于移动的方法，每次merge成功的时候，记录下当前的 ...

请问这个路径为什么能保证不会切出两个连通分量吗？

sifangyou1 发表于 2018-12-7 09:50
第五轮为什么需要next and parent pointer? 不是比较简单的题目么？dfs遍历所有节点，只要判断没有child就 ...

dfs的空间复杂度为O(h), h是树的高度

gypcmbczs 发表于 2018-12-2 07:37
楼主第二题怎么做的？先把每个id留下最小的m个在再找k个最小的吗？

那题跟面试官讨论了4种解法, 最后让写代码的是你这个

请问第一题的follow up有什么好方法吗？感觉用一定要BFS或DFS整个tree，时间复杂度O(N)?

楼主牛逼，求问第一题给一个root是什么意思？是给root 1吗？还是指root是图里任意一个点？谢谢啦

恭喜lz，请问lz有没有复习准备的方法可以分享呢