在O(1)中构造二叉树？
在O(1)中构造二叉树？
提问于 2018-03-26 23:20:11
我的朋友在一次采访中被问到这个问题：
在
O(1)中生成有限但任意大的二叉树。方法generate()应该返回一个二叉树，它的大小是无界的，但是是有限的。
我们两人在面试后考虑了很长时间，但我们只能想出最多的O(n)解决方案。
我们如何在O(1)中生成？有可能吗？还有什么别的吗？
回答 6
Stack Overflow用户
回答已采纳
发布于 2018-03-26 23:25:33
这一点被严重低估了，但对他们想要的东西进行了疯狂的猜测：
def generate():
if coinflip():
return Node()
return Node(left=None, right=generate())O(1)预期运行时，无界返回的树大小(以及无界的可能运行时，包括永远以0的概率运行)。我们随机决定是否继续使树更深，每次的概率为50%。
Stack Overflow用户
发布于 2020-08-31 18:03:49
生成一个小于可用内存大小的随机数。然后，在本地内存中选择任何长度为该长度的字节数组。
祝贺你!你刚刚创建了一个随机二叉树。二叉树的表示形式之一是数组。请参阅：tree#Arrays
Stack Overflow用户
发布于 2018-03-27 00:35:58
这既是O(1)运行时，也是无界的。树的内容是在generate()期间确定的。
#include <stdlib.h>
#include <string>
class node {
std::string _value;
unsigned int _left_seed;
unsigned int _right_seed;
bool _right_exists;
bool _left_exists;
public:
inline node(unsigned int seed,std::string const& value)
{
_value = value;
_left_seed = rand_r(&seed);
_right_seed = rand_r(&seed);
_left_exists = true; //rand_r(&seed)>5; // depends on what 'unbounded' means
_right_exists = true; //rand_r(&seed)>5;
}
inline node *get_left()
{
if (!_left_exists) return NULL;
unsigned int tseed = _left_seed;
char ch = '0' + rand_r(&tseed) % 5;
return new node(tseed,std::string(_value) + ch);
}
inline node *get_right()
{
if (!_right_exists) return NULL;
unsigned int tseed = _right_seed;
char ch = '5' + rand_r(&tseed) % 5;
return new node(tseed,std::string(_value) + ch);
}
inline const std::string& get_value()
{
return(_value);
}
};
static node *generate()
{
std::string str("");
return new node(random(),str);
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/49502112
复制相关文章
相似问题
腾讯云开发者
