实现完全二叉搜索树

题意：输入元素个数、各元素的值，实现完全二叉搜索树。
输入：5
1 2 3 4 5
输出：4 2 5 1 3

我们先考虑如何转换成一个BST，而不是complete BST。我们知道一个二叉搜索树在inorder的顺序下是一个递增序列，所以突破口就在于可以先将数列排序好，就相当于我们知道了树的inorder顺序，然后我们将其转化为level-order的顺序输出就可以了。那么如何转换呢？可以使用递归，观察数列可以发现每次parent node都出现在数列的中间位置。如 12345，那么3就是root node（注意我们现在考虑的是二叉搜索树, 不是完全二叉搜索树）那么很容易就写出了如下递归：

def change(inorder, temp, level): # change in-order into pre-order
    if inorder:
        midIdx = len(inorder) // 2
        temp.append([inorder[midIdx],level])
        change(inorder[:midIdx], temp, level+1)
        change(inorder[midIdx+1:], temp, level+1)

但是我们也注意到实际输出到temp并不是level-order，因为不是按照层的顺序摆放的，而是递归顺序摆放的pre-order。需要根据level排序后才是level-order。

1	temp = sorted(temp, key=lambda x:x[1]) # temp is the level-order of BST

重新排序完成，我们就得到了一个BST

既然实现了BST，那如何实现complete BST呢？或者说complete BST和BST有什么区别？区别就是

The encoding of a Complete Binary Search Tree as an array, A[0,…,n−1]. The root is stored at A[0], the left child of a node at index i is stored at index 2(i + 1) − 1, and its right child at index 2(i + 1).

简而言之，最底层一定是向左靠齐排满的，只有这样才能满足上面描述的要求。

假设有如下1, 2, ……., 20 总共20个点需要排列，那么BST是

           11
        /      \
      6         16
     / \       /   \
    3   9    14    19
   /\   /\   /\    /\
  2  5 8 10 13 15 18 20
 /\   /    /      /
1  4 7    12     17

最后一层并没有向左对齐排满，比如5下面就没有子节点。

那么该如何实现？有以下两种方法：

1.方法一

先截取list中间一段可以构成满二叉树的部分(part2)，按照上述方法构造满二叉树。然后再将剩下的部分(part1 & part3)交叉相融，直接添加到数列最后。只要数列长度等于$2^n-1$那么一定可以构成一个满二叉树。截取中间的一段可以使得里面任意一个点都大于part1里所有点，小于part3里所有点。

假设有如下1, 2, ……., 20 总共20个点需要排列，part1=[1, 2, 3]. part2=[4, 5, ……, 18]. part3=[19, 20]

level-order: [11, 7, 15, 5, 9, 13, 17, 4, 6, 8, 10, 12, 14, 16, 18, 1, 19, 2, 20, 3]

              11
         /           \
        7             15
     /     \         /   \
    5       9       13    17
   / \     / \      /\    /\
  4   6   8  10   12 15 16 18
 / \ / \  / 
1 19 2 20 3

代码如下：

import math # for things like log() and pow()

def buildBST(A):
    inorder = sorted(A) # turn A into in-order, the time-complexity of sorted is O(nlogn)
    Len = pow(2, int(math.log(len(A), 2)))-1 # calculate the length of A's perfect part which can built a complete BST

    # part1 and part3 are the rest of A after being cut, len(part1) should equal or one more than len(part3)
    part1 = inorder[: (len(A)-Len+1)//2]
    part2 = inorder[(len(A)-Len+1)//2: (len(A)-Len+1)//2+Len] # the perfect part of A
    part3 = inorder[(len(A)-Len+1)//2+Len: ]

    # Elegantly interleave merge part1 with part3, the combination will be added to the end of complete BST
    # the interleaved combination make it's available to be both the left and right node of any node in the last layer
    tmp = (part1, part3)
    partLast = [tmp[i % 2].pop(0) if tmp[i % 2] else tmp[1 - i % 2].pop(0) for i in range(len(part1) + len(part3))]

    # change in-order into pre-order
    temp = []
    change(part2, temp, 0)
    temp = sorted(temp, key=lambda x:x[1]) # temp is the level-order of BST
    ans = [it[0] for it in temp] + partLast # the final answer = pre-order BST + combination

    # change list A in place
    for i in range(len(A)):
        A[i] = ans[i]


def change(inorder, temp, level): # change in-order into pre-order
    if inorder:
        midIdx = len(inorder) // 2
        temp.append([inorder[midIdx],level])
        change(inorder[:midIdx], temp, level+1)
        change(inorder[midIdx+1:], temp, level+1)

2.方法二

参考, 核心思路和方法一差不多，区别只在于如何划分使得这部分list能构成complete BST。