我的 friend 在面试中被问到这个问题:
Generate a finite but arbitrarily large binary tree in
O(1)
. The methodgenerate()
should return a binary tree whose size is unbounded but finite.
面试后我们都考虑了很长时间,但我们最多只能想出O(n)
的解决方案。
我们如何在 O(1)
中生成?有可能吗?还有更多的东西吗?
最佳答案
这是非常不明确的,但可以大胆猜测他们想要什么:
def generate():
if coinflip():
return Node()
return Node(left=None, right=generate())
O(1) 预期运行时间,无限制的返回树大小(以及无限制的可能运行时间,包括以 0 概率永远运行)。我们每次以 50% 的概率随机决定是否继续使树更深。
关于algorithm - 在 O(1) 中构建二叉树?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49502112/