在O(1)中构造二叉树？

Question

我的朋友在接受采访时被问到这个问题:

生成一个有限但任意大的二叉树O(1).该方法generate()应返回一个二进制树,其大小无限但有限.

在采访之后我们都对它进行了很长时间的考虑,但我们最多只能提出O(n)解决方案.

我们将如何产生O(1)？它甚至可能吗？还有更多的东西吗？

Answer 1

这是非常不明确的,但他们想要他们想要的东西:

def generate():
    if coinflip():
        return Node()
    return Node(left=None, right=generate())

O(1)预期运行时,无界返回树大小(以及无限可能的运行时,包括永远以概率0运行).我们随机决定是否每次以50%的概率使树更深.