狗家 Intern 十月九 新OA

manyfun711 发表于 2018-10-13 06:12
O(n)的时间复杂度，O(n)的空间复杂度，用一个数组记录当前位置遍历的路径方向，然后判断深度，如果深度大于 ...

这个的确是最优解。

manyfun711 发表于 2018-10-13 06:12
O(n)的时间复杂度，O(n)的空间复杂度，用一个数组记录当前位置遍历的路径方向，然后判断深度，如果深度大于 ...

您好，可以说的更详细一些吗？没有很明白

请问楼主 第一题， 距离为D的祖先，意思就是向上找D次找到的祖先的意思么？

wang513 发表于 2018-12-1 12:27
请问楼主 第一题， 距离为D的祖先，意思就是向上找D次找到的祖先的意思么？

是zszszszszs

sunneet 发表于 2018-10-12 23:56
如果先花 O(n) 把節點建成圖
然後對圖 DFS 的時候，一邊維護一個存 path 的 queue 且長度最多為D
queue  ...

同意。但是不能用queue只能用数组记录整条path，因为假如用queue把path头上的poll掉的话会导致回溯的时候信息丢失