FB intern 跪经

应该可以不用nlogn的。如果是先explore节点，到叶子节点再统一generate path的话，每一次到达叶子节点就要把上方的父节点重复生成一遍。
如果在explore的过程当中，同时生成->的path，然后用StringBuffer存储。那么理论上可以做到真正的O(n)

楼主 第一题 时间复杂度 nlogn 面试官认可吗

harry29 发表于 2016-11-27 00:07
应该可以不用nlogn的。如果是先explore节点，到叶子节点再统一generate path的话，每一次到达叶子节点就要 ...

要把全部的path打印出来，不管怎么储存都无法避免重复的inner node吧，还是nlogn

kobe24 发表于 2016-11-27 00:50
楼主 第一题 时间复杂度 nlogn 面试官认可吗

在这和他讨论很久，后来就下一题了，不确定他到底同不同意，总之他坚持不是O(n)

我面的时候也碰到了这个题。说实话，你确实没答对。O(n), O(nlogn), O(n^2)都是可能的。要看tree的configuration。balanced tree应该是average case而不是worst case。