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

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]))

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

How to construct level order traversal using preorder and inorder traversal.(Without constructing a tree)

python

algorithm

tree-traversal