将前序遍历数组转换为级别顺序遍历数组（反之亦然），前提是二叉树是按 Level Order 填充的

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。因此，我们必须显式维护一个队列来模拟那些递归调用，而不是递归调用（即堆栈）。

我们在这里做的是，给定一个子树的根，我们首先将它添加到答案数组中。现在，与上述问题不同，查找子节点的索引具有挑战性。左边一个很容易，它会在 root 之后立即。为了找到右边的索引，我们计算左子树的总大小。这是可能的，因为我们知道它的水平填充。我们现在使用一个辅助函数 left_tree_size(n)，它 returns 在给定整棵树的大小的情况下留下子树的大小。因此，除了根的索引之外，在递归的情况下我们将传递的第二个参数是该子树的大小。为了反映这一点，我们在队列中放置了一个 (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

最后，这里是辅助函数，按照几个例子来弄清楚它为什么起作用。

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

将前序遍历数组转换为级别顺序遍历数组（反之亦然），前提是二叉树是按 Level Order 填充的

Converting a preorder traversal array to an level order traversal array (or vice versa) given that the binary tree was filled in Level Order

tree

binary-tree

tree-traversal

preorder