我正在处理一个算法问题。给定n,生成所有存储值为1…n的结构唯一的二叉搜索树。解决方案是枚举序列中的每个数字i,并将该数字用作根,其左侧的子序列1...(i-1)将位于根的左支上,同样,右侧子序列(i+1)…n将位于根的右支上。然后从子序列递归构建子树。这种方法确保构造的BST都是唯一的,因为它们具有唯一的根。
现在我的问题是:如果树不限于二叉搜索树,如果可以是任意二叉树,那么解决方案会是什么?我仍然想遍历所有根为i的情况,其中i = 1,...,n。左子树不必在1…(i-1)范围内,右子树也不必在(i+1)…n范围内。但是如何排列它们呢?创建(i-1)个元素的任意子集,然后应用?
现在我的问题是:如果树不限于二叉搜索树,如果可以是任意二叉树,那么解决方案会是什么?我仍然想遍历所有根为i的情况,其中i = 1,...,n。左子树不必在1…(i-1)范围内,右子树也不必在(i+1)…n范围内。但是如何排列它们呢?创建(i-1)个元素的任意子集,然后应用?