28810:是否同一棵二叉排序树

http://cs101.openjudge.cn/practice/28810/

给定一个插入序列就可以唯一确定一棵二叉排序树。然而，一棵给定的二叉排序树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉排序树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉排序树。

输入

输入数据的第1行给出两个正整数N (≤10)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。随后L行，每行给出N个插入的元素，属于L个需要检查的序列。

输出

对每一个需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。

样例输入

样例输出

Yes
No

来源

浙江大学 DS课程组

这个问题是典型的 二叉搜索树（BST）结构判等问题：我们需要判断多个序列在插入到 BST 中时，是否生成了和初始序列一致的结构。

🧠 解题思路：

根据初始序列构建一棵标准 BST。
对于每个待检查序列，重新构建 BST，并与标准 BST 的结构进行比较。
若结构一致，输出 "Yes"，否则输出 "No"。

✅ 判断结构一致性方法：

一种做法是对 BST 结构进行序列化（例如前序+中序），然后进行字符串比较。
也可以直接写一个结构相等判断函数，递归比较两个 BST 是否在每个结点上数值相同、左右子树结构相同。

python

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def build_bst(sequence):
    root = None
    for num in sequence:
        root = insert(root, num)
    return root

def is_same_tree(t1, t2):
    if not t1 and not t2:
        return True
    if not t1 or not t2:
        return False
    if t1.val != t2.val:
        return False
    return is_same_tree(t1.left, t2.left) and is_same_tree(t1.right, t2.right)

# 主程序
def main():
    while True:
        try:
            N, L = map(int, input().split())
            if N == 0:
                break
            base_seq = list(map(int, input().split()))
            base_tree = build_bst(base_seq)

            for _ in range(L):
                check_seq = list(map(int, input().split()))
                check_tree = build_bst(check_seq)
                print("Yes" if is_same_tree(base_tree, check_tree) else "No")
        except EOFError:
            break

# 示例输入运行
if __name__ == "__main__":
    main()

28810:是否同一棵二叉排序树 ​

28810:是否同一棵二叉排序树