如何使用前序和顺序遍历构造层次顺序遍历（不构造树）

Question

顺序=[1,2,3,4,5,7,6,8,9,10,11,12,13,14,15]

这是顺序遍历

• 正如trinkot在评论中所说的，我们不能只使用顺序遍历来构造二叉树。假设也给出了任意随机的前序遍历。如何在不创建树的情况下找到级别顺序遍历

我想要像这样的水平顺序遍历

levelorder=[8,4,12,2,6,10,14,1,3,5,7,9,11,13,15]

我想过使用递归函数，比如

def rec(lis):
    if(len(lis)<1):
        return
    mid = len(lis)//2
    root = lis[math.ceil(mid)]
    array.append(lis[root])
    rec(lis[0:mid])
    rec(lis[mid+1:])

但这不起作用，因为第二个递归调用只在所有第一个递归调用结束后发生。 有没有办法让我交替调用第一个和第二个递归调用

或者有没有其他方法可以在不构建树的情况下找到树的层次顺序遍历

Answer 1

当然，为什么不呢？ 这不是最有效的实现，但适当的数据结构支持将使其达到渐近最优

def level_order(pre_order):
    path = []
    levels = []
    for x in pre_order:
        while path and any(path[-1] < y < x for y in path):
            del path[-1]
        path.append(x)
        while len(levels) < len(path):
            levels.append([])
        levels[len(path) - 1].append(x)
    return [x for level in levels for x in level]


print(level_order([8, 4, 2, 1, 3, 6, 5, 7, 12, 10, 9, 11, 14, 13, 15]))