【随机生成二叉树的问题】

Question

bobo大大大大佬好，这是我自己想的根据数组随机生成一棵二叉树的，思路是先随机打乱数组，然后生成二叉树，但是现在***遇到的问题是二叉树的结构不是随机的***，总是偏向一边，我虽然知道是***if语句出了问题，但是想了好久也不知道怎么改***

public class Solution2 {

	Random random = new Random(System.currentTimeMillis());

	//根据数组随机生成一棵二叉树
	public TreeNode generateTree(int[] array){
		randomArray(array);
		return dfs(array,0);
	}

	private TreeNode dfs(int[] array,int index){
		TreeNode node = new TreeNode(array[index]);
		if(index == array.length -1){
			return node;
		}
		int flag = random.nextInt(2);
		//这里有问题 但是感觉无从下手
		if(flag % 2 == 0){
			node.left = dfs(array,index + 1);
		}else {
			node.right = dfs(array,index +1);
		}
		return node;
	}


	private void randomArray(int[] array){
		//bobo老师的公众号的随机算法
		for(int i = array.length -1; i >= 0; i --){
			swap(array,i,random.nextInt( i +1));
		}
	}

	private void swap(int[] array,int aIndex, int bIndex){
		int c = array[aIndex];
		array[aIndex] = array[bIndex];
		array[bIndex] = c;
	}



}

Answer 1

liuyubobobo 2020-05-21 09:56:36

我不确定我是不是正确理解了你的问题，但现在你的代码，每一个节点，或者只是左边有子树，或者只是右边右子树，这是你想要的结果吗？因为你的 dfs 中，或者只对 node.left 进行了赋值；或者只对 node,right 进行了赋值。

一个更好的思路是，随机完整个数组以后，创建一个子函数，根据 array[l...r] 的元素生成一棵随机二叉树。初始根据array[0...n-1] 生成一棵随机二叉树。

每一次，在 [l...r] 区间内随机一个索引 index，当前的节点取 array[index] 的值；

然后，当前节点的左子树根据[l...index-1] 生成随机二叉树；

当前节点的右子树根据[index+1...r] 生成随机二叉树；

依次递归。

试试看？

如果对这类问题不熟悉，可以先尝试解决搞懂 Leetcode 上的 105，106，889，1008 和 297。

加油！：）