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

Question

我的朋友在面试中被问到这个问题：

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% 的概率随机决定是否继续使树更深。

Answer 2

这既是 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);
}

Answer 3

https://www.dailycodingproblem.com/blog/big-tree/

import random

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def generate():
    root = Node(0)

if random.random() < 0.5:
    root.left = generate()
if random.random() < 0.5:
    root.right = generate()

return root

Answer 4

生成一个小于可用内存大小的随机数。然后，在本地内存中选择该长度的任何字节数组。

恭喜！您刚刚创建了一个随机二叉树。二叉树的一种表示形式是数组。参见：https://en.wikipedia.org/wiki/Binary_tree#Arrays

Answer 5

这是愚蠢面试问题的一个很好的例子。

解决方案是生成单个节点并 return 它。这棵树的特别之处属性 getLeft() 和getRight() 是一个facade，在调用函数时生成节点，而不是预先创建所有节点。

public static void main(String args[]) {
  Node root = new Node(); // O(1)
}

public class Node {
  private Node left, right;
  private boolean isLeftEvaluated = false, isRightEvaluated = false;

  public Node getLeft() {
    if (! isLeftEvaluated) {
      left = new Node();
    }

    isLeftEvaluated = true;
    return left;
  }

  public Node getRight() {
    if (! isRightEvaluated) {
      right = new Node();
    }

    isRightEvaluated = true;
    return right;
  }
}

任何具有良好编程经验的人都不会考虑这种未指定需求的解决方案。

Answer 6

我稍微分析了一下需求。他们没有说他们想要什么样的树，（完整的，倾斜的等等），也没有说底层的数据结构。所以如果我们假设他们想要一棵完全二叉树，那么任何数组都可以认为是一棵完全二叉树。所以我们可以 return 一个任意大小的数组。要填充 (1) 中的数组，我们可以使用类似 memcopy 的东西来填充它的垃圾值。或者，如果它是用类似 c 的语言实现的，则使用现有的垃圾值作为数据。这是我刚刚想到的。这可能根本不对。同样，要求非常模糊。

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

Construct Binary Tree in O(1)?

algorithm

binary-tree

time-complexity