algorithm - 在不构造红黑树的情况下获得广度优先（级别）顺序

Question

n我有一个包含连续整数元素1的有序长度数组n。在为这个数组构建红黑树之后，我可以使用标准的广度优先搜索方法按级别顺序遍历这棵树。

我的问题是，给定任何（对应于具有从ton <= 100000000连续整数元素的有序数组），是否可以绕过树的构造并直接返回级别顺序？1n

标签： algorithmbinary-search-treebreadth-first-search

Answer 1

如果你不介意额外的空间，你可以这样做。

def level_order(n):
    queue = [(1, n)]
    i = 0
    while i < len(queue):
        a, b = queue[i]
        i += 1
        if a > b:
            continue
        m = (a + b) // 2
        yield m
        queue.append((a, m - 1))
        queue.append((m + 1, b))


print(list(level_order(13)))