我想知道排序数组（例如[1，2，3，4，5，6]）和从该排序数组构造完整的二进制搜索树并将所述二进制搜索树表示为数组时获得的表示之间是否存在映射（例如[4，2，6，1，3，5]，见下图）？
4
2 6
1 3 5
这里还有一些上下文：众所周知，可以使用排序数组并从中构建一个完整的二进制搜索树（有一个唯一的表示）。递归算法是：找到合适的mid（这实际上很棘手），将其视为根，然后在左子数组和右子数组上递归。根据得到的BST，可以执行级别顺序遍历（基本上是广度优先搜索）来构建完整BST的数组表示。
我之所以这么问，是因为这个映射与数组的内容无关：它只取决于数组的长度。因此，我觉得应该可以将两个数组简洁地表示为彼此的函数。
有什么想法吗？
树的高度是可预测的roundUp(log2(nodes))。我们也知道，右子树never大于左子树-|LS| >= |RS|。此外，我们还可以计算缺失的节点数量，以使树完美：2 ^ (height - 1) - arr.length。这使我们能够预测如何在子树之间分配节点：
findRoot(int[] arr , int maxLeaves , int maxLevelL)
//maxLeaves is the number of leaves on the maximum-level
int l = min(maxLevelL / 2 , maxLeaves)
return (arr.length - maxLeaves) / 2 + l
node buildTree(int[] arr , int maxLeaves , int maxLevelL)
if maxLevelL == 0
return null
node result
int rootidx = findRoot(arr , maxLeaves)
result.val = arr[rootidx]
result.left = buildTree(arr.subarray(0 , rootidx) , Math.min(maxLeaves , rootidx - 1) , maxLevelL / 2)
result.right = buildTree(arr.subarray(rootidx + 1 , arr.length) , Math.max(0 , maxLeaves - rootidx - 1) , maxLevelL / 2)
return node
基本思想如下：所有完整的BST共享一个属性，关于BST的递归定义：(LS , R , RS) OR null，其中LS和RS是左子树和右子树，它们也被定义为BST。CCD_ 7和CCD_。我们可以很容易地预测两者中的哪一个是完美的：在最高级别上拟合m节点，但在阵列中我们缺少x节点来构建完美的树。因此：
if m - x == m / 2 then both are complete and the height of RS is height(LS) - 1
if m - x < m / 2 RS is perfect, LS only complete but not perfect
if m - x > m / 2 LS is perfect, RS only complete but not perfect
if m - x == 0 both LS and RS are perfect and of equal height
我们可以使用以下规则找到树的根：计算左侧（l）和右侧（r）子树上将被放置在最高级别上的节点数。现在，我们可以很容易地从树中删除这些节点，计算完美BST的根，然后隐式地将左右节点添加回树中：root = (arr.length - (l + r)) / 2 + l
E.g.:
Input: 1 2 3 4 5
Nodes on maxLevel: 2
maxLevelL: 4
l = 2
r = 0
root_idx = (arr.length - (l + r)) / 2 + l =
= (5 - 2) / 2 + 2 =
= 3
Apply this algorithm recursively to define subtrees:
...
result:
4
/
2 5
/
1 3
注意：我还没有测试过这个代码。可能是它仍然包含一些需要修复的算术不足。不过，逻辑是正确的。这应该只是表示将索引从一个数组重新映射到另一个数组的一种方式。实际的实现可能与我提供的代码有很大不同。
在第二次讨论之后，这里有一个完整BST的定义：
在一个完整的二叉树中，除了最后一级之外，每一级都是完全填充的，并且最后一级中的所有节点都尽可能地向左。
来自维基百科
完整BST是平衡BST的一个子类，带有一些额外的约束，允许将完整BST唯一映射到排序数组，反之亦然。由于完整的BST只是平衡BST的一个子类，因此不足以构建平衡BST。
编辑：
可以通过以下方式更改上述算法以直接构建阵列：
- 树根的索引为0
- 索引为CCD_ 14的节点的左子节点具有索引CCD_
- 索引为
n的节点的右子节点具有索引(n + 1) * 2
通常这些访问操作是在基于1的数组上完成的，但为了方便，我已经将它们更改为匹配基于0的数组
因此，我们可以重新实现buildTree，直接生成一个数组：
node buildTree(int[] arr , int maxLeaves , int maxLevelL ,
int[] result , int nodeidx)
if maxLevelL == 0
return
int rootidx = findRoot(arr , maxLeaves)
//insert value into correct position of result-array
result[nodeidx] = arr[rootidx]
//build left subtree
buildTree(arr.subarray(0 , rootidx) , Math.min(maxLeaves , rootidx - 1) , maxLevelL / 2 ,
result , (nodeidx + 1) * 2 - 1)
//build right subtree
buildTree(arr.subarray(rootidx + 1 , arr.length) , Math.max(0 , maxLeaves - rootidx - 1) , maxLevelL / 2 ,
result , (nodeidx + 1) * 2)
注意，与arr不同，我们从不使用result的任何子阵列。在任何方法调用中，各个节点的索引都不会改变。
以下是我的想法。它并不理想，因为它不是我心目中的功能，但它节省了构建树然后从中创建数组的工作量
find_idx(n) {
if n == 1 { return 0; }
h = ceil(lg(n+1)) // height of the tree
f_h = floor(lg(n+1)) // height of the full portion (h or h-1)
m_n = 2^h - 1 // # of nodes if tree were full
f_n = 2^f_h -1 // # of nodes of full portion
return floor(f_n / 2) + min(n - f_n, floor((m_n - f_n) / 2)
}
to_bst_array(array) {
q = new empty queue
res = resulting vector
q.push(array)
while !q.is_empty() {
subarray = q.pop()
idx = find_idx(subarray.len())
res.push(subarray[idx])
if subarray.len() > 1 {
q.push(subarray[..idx]) // slice from 0 to idx
}
if subarray.len() > idx + 1 {
q.push(subarray[idx + 1..]) // slice from idx+1 till end of subarray
}
}
return res
}
这是我解决这项任务的方法，希望你喜欢！）
def GenerateBBSTArray(a):
a.sort()
level = 0
accum = []
elements = []
while len(a) // 2**level > 0:
accum = [elem for elem in a[len(a) // 2**(level + 1)::(len(a) // 2**level) + 1]]
elements.extend(accum)
accum = []
level += 1
return elements
在表示二进制树搜索（BST）和直接排序数组之间没有直接表示。排序数组之间的唯一关系是在BST上按顺序遍历并将其存储在数组中时。