新鲜的狗家 intern 电面

cmh000111 发表于 2018-9-6 03:35
想问下楼主删掉node不留空是什么意思？前两问删掉node之后子树是怎么处理的？

第一问删掉后留下 null，从第二问之后都是后面的往前移

第二题第一问，如果是tree里面需要访问所有的leave的话， 难道不是把所有的edge cost都加起来么 。。

qwqw 发表于 2018-10-2 16:17
第二题第一问，如果是tree里面需要访问所有的leave的话， 难道不是把所有的edge cost都加起来么 。。

我理解的就是找最长的路径，这个路径走完就把所有的孩子都灌满了。需要把这条路径的 cost 加起来

请问楼主第一题可以读入输入以后自己构建树吗？还是要全程用他给的这个结构进行操作？

楼主 请问第二轮的第三问 是不是等于就是将单源最短路径 变成了 多源最短路径？用Floyd-Warshall可以吗？

dengzeyu147 发表于 2018-10-10 07:16
楼主 请问第二轮的第三问 是不是等于就是将单源最短路径 变成了 多源最短路径？用Floyd-Warshall可以吗？

我当时回答的就是 对于每一个 node 每次 cache 一下最短的路，有点类似于 dp 的感觉，感觉面试官是认可的，当时也没有细想

桃桃126816 发表于 2018-10-10 07:43
我当时回答的就是 对于每一个 node 每次 cache 一下最短的路，有点类似于 dp 的感觉，感觉面试官是认可的 ...

哦哦哦 okay 明白你的想法了