新鲜狗家阳谷昂赛

"找到tree 里面一个node的K th ancestor。 记得是蠡口原题但是不记得题号了。限制用O(K) space. Backtraking。"

没太看懂。如果空间限制是K, 那么只能做morris traversal 了？

第六题用树吗？比如a{b, c{d, e}}这个就是a 是根，b 还有 c{d, e}是a的children，然后d， e是c的children, dfs找所有从根到叶的路径？Parse的时候递归成树？

第6轮输出的规律是什么啊。。

qiweiwang89 发表于 2019-3-4 10:43
对的就这个意思，说起来当时面试官当场把手上的戒指拿来给我看。。。。。

请问多余的边是否影响TRUE/FALSE的判断呢？
比如
0: 1, 2
1: 0, 2, 3
2: 0, 1, 3
3: 1, 2
如果走0-1-3-2-0 就能是个完整的ring。但是1-2有个边，是否因为这个边而回答FALSE呢？

补充内容 (2019-3-5 00:26):

1. 
   
2.     0
   
3.   /   \
   
4. 1 --- 2
   
5.   \   /
   
6.     3
   

复制代码

14417335 发表于 2019-3-5 00:16
请问多余的边是否影响TRUE/FALSE的判断呢？
比如
0: 1, 2

我问了面试官同样的问题，答案是不算

Kanchine 发表于 2019-3-4 14:36
第六题用树吗？比如a{b, c{d, e}}这个就是a 是根，b 还有 c{d, e}是a的children，然后d， e是c的children,  ...

我后来基本是往这个方向想的，但是没写出来

qiweiwang89 发表于 2019-3-5 01:11
我问了面试官同样的问题，答案是不算

求hamilton cycle吗还是我想多了？

qiweiwang89 发表于 2019-3-5 01:12
我后来基本是往这个方向想的，但是没写出来

谢楼主回复！

第六题可以{a,b}{c,d}吗？还是说｛只链接字母

第六题用递归好做一些哈