本文共 1181 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要判断两个序列是否可以构建同一棵二叉排序树。二叉排序树的定义是：左子树中所有节点的值均小于根节点的值，右子树中所有节点的值均大于根节点的值。我们可以通过生成每个序列的预序序列来比较它们是否构建了同一棵树。

方法思路

解决代码

def generate_preorder(s):    if not s:        return ""    min_val = min(s)    left = [x for x in s if x < min_val]    right = [x for x in s if x > min_val]    left_pre = generate_preorder(''.join(left))    right_pre = generate_preorder(''.join(right))    return f"{min_val}{left_pre}{right_pre}"n = int(input())sequences = []while True:    try:        s = input().strip()        sequences.append(s)    except EOFError:        breakif not sequences:    print("NO")else:    first = sequences[0]    pre_first = generate_preorder(first)    for s in sequences[1:]:        pre = generate_preorder(s)        if pre == pre_first:            print("YES")        else:            print("NO")

代码解释

通过这种方法，我们能够高效地判断两个序列是否可以构建同一棵二叉排序树。

转载地址：http://medyz.baihongyu.com/