https://docs.google.com/document/d/1qxA2wps0IhVRWULulQ55W4SGPMu2AE5MkBB37h8Dr58/
第三轮，三哥，题目就一句话，让我先随机构造一颗size为N的树。我开始没听到“random”一词，就以为构成一颗树就行。秉着论坛经验贴说的，要提前考虑各种条件。我就开始问他，有木有其他限制，比如形状有木有要求，普通的树还是二叉树，N<=0怎么办等等。。。他就说没有，只要size是N就行了
https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence
构造一棵size为n的随机树
第三轮，三哥，题目就一句话，让我先随机构造一颗size为N的树。我开始没听到“random”一词，就以为构成一颗树就行。秉着论坛经验贴说的，要提前考虑各种条件。我就开始问他，有木有其他限制，比如形状有木有要求，普通的树还是二叉树，N<=0怎么办等等。。。他就说没有，只要size是N就行了
0 1
/ / \
1 2 0
/
2
如果要求上图是不同的两棵树（虽然它们选择的边都相同，但是根不同），可以用以下思路
- pool初始化为[1,2,3, … n]
- 从pool中随机选择一个vertex V准备加入tree
- 从tree中随机选择一个vertex U作为V的父亲节点
- 将v从pool中删除，加入u的孩子中
- 重复从2开始，直到pool为空
构造
0 => P = ⅓
/
1 => P = ½
/
2 => P = ½
概率：P = 1/12
0 0 0 0 root == 0，4 situations, total == 12 situations
/ / / \ / \
1 2 1 2 2 1
/ /
2 1
参考代码：
Provider: null
private class TreeNode{
int val;
List<TreeNode> children;
public TreeNode(int x) {
val = x;
children = new ArrayList<>();
}
}
public TreeNode getTree(int N) {
if(N == 0) return null;
List<TreeNode> pool = new ArrayList<>();
for(int i = 0 ; i < N; i++) {
pool.add(new TreeNode(i));
}
List<TreeNode> tree = new ArrayList<>();
Random rand = new Random();
while (pool.size() > 0) {
int idx = rand.nextInt(pool.size());
TreeNode curr = pool.get(idx);
if(tree.size() == 0) {
tree.add(curr);
pool.remove(idx);
} else {
int parent = rand.nextInt(tree.size());
tree.get(parent).children.add(curr);
tree.add(curr);
pool.remove(idx);
}
}
return tree.get(0);
}
Time complexity: o(n^2)
如果题目要求是构造一棵无根的label tree
0 1
/ / \
1 2 0
/
2
一张n个顶点的联通图中构造一棵随机的生成树，上图两树被看作一棵树
思路: 先构造随机的Prüfer sequence，然后根据sequence生成树
(cayley’s formula中用到的树的表示方法)
Time complexity: O(n ^ 2)
参考代码
Provider: null
public Map<Integer, List<Integer>> getRandomTree(int n) {
if(n <= 2) {
Map<Integer, List<Integer>> tree = new HashMap<>();
for(int i = 0 ; i < n ; i++) {
tree.put(i, new ArrayList<>());
}
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < n ; j++) {
if(i != j) {
tree.get(i).add(j);
tree.get(j).add(i);
}
}
}
return tree;
}
int[] prufer = new int[n - 2];
Random rand = new Random();
for(int i = 0 ; i < prufer.length ; i++) {
prufer[i] = rand.nextInt(n);
}
return getTree(prufer);
}
// 根据prufer sequence得到label tree
public Map<Integer, List<Integer>> getTree(int[] prufer) {
int n = prufer.length + 2;
Map<Integer, List<Integer>> tree = new HashMap<>();
for(int i = 0 ; i < n ; i++) {
tree.put(i, new ArrayList<>());
}
int[] vertices = new int[n];
for(int x : prufer) {
vertices[x]++;
}
for(int i = 0 ; i < prufer.length ; i++) {
for(int j = 0 ; j < vertices.length ; j++) {
if(vertices[j] == 0) {
// connect j <--> prufer[i]
tree.get(j).add(prufer[i]);
tree.get(prufer[i]).add(j);
vertices[j] = -1; // delete from vertex set
vertices[prufer[i]]--; //delete from prufer set
break;
}
}
}
// connect the last two vertex with vertices[i] == 0
Integer first = null;
for(int i = 0 ; i < vertices.length ; i++) {
if(vertices[i] == 0) {
if(first == null) first = i;
else {
tree.get(first).add(i);
tree.get(i).add(first);
break;
}
}
}
return tree;
}
