狗狗实习两轮面经，求打捞，求鱼塘群～

chengshuangdao 发表于 2018-1-16 23:22
这个你说的有道理。。。我这里好像默认假设所有node unique了，也不记得有没有跟面试官确认过。。
但是 ...

多谢楼主解答，祝早日match：）

rippersean 发表于 2018-1-17 02:10
楼主第一题能不能直接把树弄成数组，空的加null，这样子从根开始左右子树分别指针跳转去做类似dfs的查找？

但是这样做和直接用treenode class做dfs有什么区别呢？

fisherhust 发表于 2018-1-17 01:22
恭喜楼主, 祝早日match

谢谢～紫薯紫薯紫薯

appleLeaf 发表于 2018-1-17 02:22
多谢楼主解答，祝早日match：）

谢谢～紫薯紫薯紫薯

请问楼主，第二题，是要生成一条，还是所有的路径呢，随机生成一条左上角到右下角的路径后，为什么还要shuffle呢，谢谢

wjw779 发表于 2018-1-17 07:05
请问楼主，第二题，是要生成一条，还是所有的路径呢，随机生成一条左上角到右下角的路径后，为什么还要shuf ...

生成一条就好了。shuffle是为了backtracking，因为如果你每次只是单纯随机选一个方向，这个路径可能走不到右下角或者成环，所以需要backtracking，shuffle一个数组保证了随机，以及不重复走选过的方向

楼主能详细说一下第一题是怎么用map优化到O(n)的吗?多谢

dongsancu 发表于 2018-1-23 06:50
楼主能详细说一下第一题是怎么用map优化到O(n)的吗?多谢

对两棵树同时bfs，一层层来，对于每层bfs，除了记录这一层的nodes，还要用一个Map<Node, Node> 来记录每个node的parent，那么对于每一层，除了保证nodes要完全相同。还要保证相同node的parent也必须一样。然后每次bfs到下一层，更新nodes的同时也要更新放parents的map

chengshuangdao 发表于 2018-1-23 07:12
对两棵树同时bfs，一层层来，对于每层bfs，除了记录这一层的nodes，还要用一个Map 来记录每个node的paren ...

明白了。多谢多谢

chengshuangdao 发表于 2018-1-17 07:29
生成一条就好了。shuffle是为了backtracking，因为如果你每次只是单纯随机选一个方向，这个路径可能走不 ...

楼主的意思是shuffle directions么？