将前序遍历数组转换为级别顺序遍历数组（反之亦然），因为二叉树以级别顺序填充

Question

假设您有一个按级别顺序填充的二叉树，即每个级别都在该级别节点的任何子级之前填充。这样的树可以通过其水平顺序遍历来唯一定义。例如 {1，2，3，4，5，6} 是

    1
 2     3
4 5   6

对其进行预序遍历将生成数组{1,2,4,5,3,6}

有没有办法将这些数组中的一个直接转换为另一个数组，这比生成实际树并在其上预先形成实际遍历更快？（对于具有 n 个节点的树）

Answer 1

是的，这两者都可以在一次通过中实现。

首先，升级到预订，因为这更容易一些。由于这是一个级别填充的树，对于数组中的任何节点，给定它的索引 i，左子树节点的索引公式为 2*i 1，右为 2*i 2。因此，我们以预序递归方式调用它们，将根节点附加到所需数组的后面。

def level_to_pre(arr,ind,new_arr):
    if ind>=len(arr): return new_arr #nodes at ind don't exist
    new_arr.append(arr[ind]) #append to back of the array
    new_arr = level_to_pre(arr,ind*2+1,new_arr) #recursive call to left
    new_arr = level_to_pre(arr,ind*2+2,new_arr) #recursive call to right
    return new_arr

并像这样调用它，这里将填充最后一个空白数组。

ans  = level_to_pre([1,2,3,4,5,6],0,[])

在我进入前级到级别部分之前，请记住dfs使用递归，它在场景后面使用堆栈。而bfs使用队列。我们手中的问题，按级别优先顺序填充数组，基本上是bfs。因此，我们将不得不显式维护一个队列来模拟这些递归调用，而不是递归调用（即堆栈）。

我们在这里做的是，给定子树的根，我们首先将其添加到答案数组中。现在，寻找子节点的索引很有挑战性，不像上面的问题。左一个很容易，它会紧跟在根之后。为了找到右的索引，我们计算左子树的总大小。这是可能的，因为我们知道它已经填满了级别。我们现在使用一个帮助函数left_tree_size（n），它在给定整棵树的大小的情况下返回左子树的大小。所以，除了root的索引之外，我们在递归情况下要传递的第二个参数是这个子树的大小。为了反映这一点，我们在队列中放置一个（root， size）元组。

from math import log2
import queue

def pre_to_level(arr):
    que = queue.Queue()
    que.put((0,len(arr)))
    ans = [] #this will be answer
    while not que.empty():
        iroot,size = que.get() #index of root and size of subtree
        if iroot>=len(arr) or size==0: continue ##nodes at iroot don't exist
        else : ans.append(arr[iroot]) #append to back of output array
        sz_of_left = left_tree_size(size) 
        que.put((iroot+1,sz_of_left)) #insert left sub-tree info to que
        que.put((iroot+1+sz_of_left,size-sz_of_left-1)) #right sub-tree info 

    return ans

最后，这里是helper函数，下面是一些示例，以了解其工作html" target="_blank">原理。

def left_tree_size(n):
    if n<=1: return 0
    l = int(log2(n+1)) #l = no of completely filled levels
    ans = 2**(l-1)
    last_level_nodes = min(n-2**l+1,ans)
    return ans + last_level_nodes -1