algorithm - 在 O(1) 中构建二叉树？

Question

我的 friend 在面试中被问到这个问题:

Generate a finite but arbitrarily large binary tree in O(1). The method generate() should return a binary tree whose size is unbounded but finite.

面试后我们都考虑了很长时间，但我们最多只能想出O(n) 的解决方案。

我们如何在 O(1) 中生成？有可能吗？还有更多的东西吗？

Answer 1

这是非常不明确的，但可以大胆猜测他们想要什么:

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

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