Linkedin二面面经

wjl2525 发表于 2014-10-17 13:09
我看不到题目，层主能麻烦你简单复述下题目要求吗？谢谢啦。

我的理解就是原来这棵树是任意的树，现在transform成满n叉树，然后新的树要保持原来的parent/children的关系，children最多变为parent的sibling，不能成为parent的parent，太绕了，希望你明白了，不过这也是我对这题的理解，哈哈

应该就是任意树转满N叉树，父子关系不准颠倒，但是可以变成同辈。建一个长为N的队列，从根到叶广度优先跑一遍就可以了吧。

我点不开姐姐。不过看上面的评论应该2叉转满N叉没错？N是给定的还是自己找？

BFS可行 但是有个问题 比如12345 是二叉树 要变三叉树 多出来一个元素怎么处理 他要节点孩子不是n就是0. 还是说节点个数在n范围内就可以。

traceroute_su 发表于 2014-10-19 03:11
BFS可行 但是有个问题 比如12345 是二叉树 要变三叉树 多出来一个元素怎么处理 他要节点孩子不是n就是0. 还 ...

这个问题如果首先就问清楚， 在面试官那肯定是加分的。

traceroute_su 发表于 2014-10-19 16:11
BFS可行 但是有个问题 比如12345 是二叉树 要变三叉树 多出来一个元素怎么处理 他要节点孩子不是n就是0. 还 ...

题里说了，只有一个点可以是例外，其儿子数目介于0到N之间。所以我觉得跑一遍BFS把新树尽量堆满就行了……

3652ltc 发表于 2014-10-17 13:07
我怎么觉得第二题很难呢。。。如果用一个queue先把树存下来，有点浪费空间，可以满了的话就添加在新树上,不 ...

谢谢解答，想问下你这里开两个queue的用途？你的new_q进入循环后只有pop没有push操作（pop一次就空了吧），不知道我有没有看错？

traceroute_su 发表于 2014-10-19 16:11
BFS可行 但是有个问题 比如12345 是二叉树 要变三叉树 多出来一个元素怎么处理 他要节点孩子不是n就是0. 还 ...

可以有一个exception

billupus 发表于 2014-10-18 05:05
我点不开姐姐。不过看上面的评论应该2叉转满N叉没错？N是给定的还是自己找？

N是给定的，我补充了文字说明你可以看看

billupus 发表于 2014-10-18 05:05
我点不开姐姐。不过看上面的评论应该2叉转满N叉没错？N是给定的还是自己找？

N是给定的，我补充了文字说明你可以看看