是否同一棵二叉搜索树pta

### 判断两组序列是否可以构建出相同的二叉搜索树 要解决此问题，可以通过模拟二叉搜索树（BST）的构造过程来实现。具体方法如下： #### 方法概述 给定一组前序遍历序列和多组待验证序列，分别按照这些序列插入节点并构建 BST。如果某组待验证序列所生成的 BST 结构与初始序列一致，则输出 “Yes”，否则输出 “No”。 以下是详细的解决方案。 --- #### 输入解析 根据描述[^3]，输入包含多个测试案例。对于每个测试案例： 1. **第一行**：两个整数 N 和 L，表示序列长度以及需要检查的序列数量。 2. **第二行**：N 个正整数，代表初始插入序列。 3. **后续 L 行**：每行为一个待验证序列，长度同样为 N。 --- #### 实现逻辑 为了判断两组序列是否能生成相同结构的 BST，需遵循以下步骤： 1. 定义一个函数 `build_bst` 来基于任意序列构建 BST 的字符串化表达形式（便于比较）。 2. 使用递归方式完成 BST 构建，并记录每次插入后的状态。 3. 针对初始序列和所有待验证序列调用上述函数，逐一比较它们的结果。 下面是完整的 Python 实现代码： ```python class TreeNode: def __init__(self, val=0): self.val = val self.left = None self.right = None def build_bst(sequence): """ 根据序列构建 BST 并返回其字符串化表达 """ root = None def insert(node, value): nonlocal root if not node: new_node = TreeNode(value) if not root: # 如果当前为空树，则设置根节点 root = new_node return new_node elif value < node.val: node.left = insert(node.left, value) else: node.right = insert(node.right, value) return node def serialize(node): """ 序列化 BST 节点用于唯一标识一棵树 """ if not node: return "#" left_str = serialize(node.left) right_str = serialize(node.right) return f"{node.val},{left_str},{right_str}" for num in sequence: root = insert(root, num) return serialize(root) # 主程序处理输入 import sys input = sys.stdin.read data = input().strip().split("\n") index = 0 results = [] while index < len(data): # 处理多组测试数据 n_l = data[index].split() N, L = int(n_l[0]), int(n_l[1]) initial_sequence = list(map(int, data[index + 1].split())) base_tree_serialized = build_bst(initial_sequence) # 构造基础树 checks = [] for i in range(L): check_sequence = list(map(int, data[index + 2 + i].split())) current_tree_serialized = build_bst(check_sequence) checks.append(current_tree_serialized == base_tree_serialized) results.extend(["Yes" if c else "No" for c in checks]) index += 2 + L print("\n".join(results)) ``` --- #### 关键点说明 1. **BST 插入规则**：新值小于父节点则进入左子树；大于等于父节点则进入右子树。 2. **序列化机制**：通过先序遍历的方式将整个树转换成唯一的字符串表示，从而方便对比不同树之间的差异。 3. 时间复杂度分析：单次构建操作的时间复杂度为 O(N)，因此总时间复杂度约为 O((L+1)*N)。 --- #### 测试样例 假设输入如下： ``` 5 2 8 6 9 4 7 8 6 4 7 9 8 9 6 4 7 ``` 运行结果应为： ``` Yes No ``` 解释： - 第一种情况下的插入顺序能够重现原始 BST； - 第二种情况下无法得到完全匹配的结构。 ---