来做这道题之前我一直以为自己很懂二叉搜索树。直到《数据结构》第四章的“04-树4 是否同一棵二叉搜索树”把我挂了好几回我才意识到题目里“同一棵”这三个字比听上去重得多。二叉搜索树Binary Search TreeBST的插入规则并不复杂但同一种树形可以由多种插入顺序生成而判断两组插入顺序最后是不是产生完全一样的树并不能靠“把序列排个序再比较”这种偷懒办法。这道题在 MOOC《数据结构》和 PTA 平台上都很有名适合刚学完树、想真正理解 BST 结构本质的人拿来练手。1. 题面拆解什么是“同一棵”二叉搜索树1.1 从两条插入序列看“结构相同”二叉搜索树的插入规则不复杂小的往左大的往右遇到空位就挂上去。按这个规则给定一个插入序列最终树形完全确定。但反过来不成立——同一棵树可以由很多不同序列得到。举个例子插入序列{2, 1, 3}最终得到2 / \ 1 3换成{2, 3, 1}呢先插 2根是 2再插 33 比 2 大挂在右边最后插 11 比 2 小挂在左边。最终还是一模一样的树。所以这两个序列属于“同一棵二叉搜索树”。但是如果给{1, 2, 3}先从 1 开始根变成 12 比 1 大挂在右边3 比 2 大继续挂在右边。最后得到一条向右歪的链1 \ 2 \ 3根都不一致当然不是同一棵。这个区分很关键所谓“同一棵”并不是指元素集合相同也不是指中序遍历结果相同而是指树的结构和每个位置上的节点值都完全一致。1.2 原题输入输出格式与两条关键约定这道题在《数据结构》MOOC 和 PTA 平台上一般长这样多组测试数据每组第一行给两个整数 N 和 LN 是每个插入序列的元素个数L 是需要检查的序列数第二行给 N 个整数作为初始插入序列接下来有 L 行每行也全是 N 个整数是需要验证的候选序列。读到 N 等于 0 时结束。常见样例4 2 3 1 4 2 3 4 1 2 3 2 4 1 0对应输出Yes No这里有两个容易被忽略的约定。第一个题目保证每个插入序列都是 1 到 N 的一个排列意味着每个序列中不会出现重复数字不同序列包含的元素集合也完全相同只是顺序不同。第二个判断对象是“以这些数字为插入序列生成的二叉搜索树”而不是直接比对序列内容。否则样例里{3, 1, 4, 2}和{3, 4, 1, 2}序列不同却要输出 Yes直接按序列比较就全错了。理解到这里再动手写代码才有意义。2. 第一版提交建两棵树再递归比较2.1 节点定义和插入函数的写法最自然的做法是把基准序列建一棵树把候选序列也建一棵树然后递归比较这两棵树。先定义节点结构。除了值和左右子树指针我为后面的标记法提前准备一个 flag 字段第一版用不到但留着不碍事typedef struct TNode { int v; struct TNode *left; struct TNode *right; int flag; } *Tree;插入函数是 BST 的基本功Tree insert(Tree T, int v) { if (T NULL) { T (Tree)malloc(sizeof(struct TNode)); T-v v; T-left NULL; T-right NULL; T-flag 0; return T; } if (v T-v) { T-left insert(T-left, v); } else { T-right insert(T-right, v); } return T; }既然题目给的是排列值不会重复所以插入时只需要处理小于和大于两个分支。如果题目不保证不重复这里还得想清楚相等的元素往哪边挂判断逻辑会复杂不少。2.2 比较函数完全相同不等于同构两棵树“完全相同”的判断写成递归int isSame(Tree A, Tree B) { if (A NULL B NULL) return 1; if (A NULL || B NULL) return 0; if (A-v ! B-v) return 0; return isSame(A-left, B-left) isSame(A-right, B-right); }这里的递归出口想清楚就很简单两边都为空相同一边为空另一边不为空不同当前根的值不一样不同当前根一样还要左子树相同、右子树相同。有一个概念容易混淆树的“同构”和这里的“相同”并不一样。同构通常允许左右子树互换比如节点 A 有左孩子 1、右孩子 2B 有左孩子 2、右孩子 1在某些同构定义下也算同构但肯定不是“同一棵二叉搜索树”。这道题要求的是结构和节点值全部一致不能互换。2.3 一遍遍建树的代价与内存习惯用这个方案解这道题性能完全够。N 不超过 10L 也不会很大最坏情况每次建树也就是 10 个节点。但作为一个练手项目我建议还是把释放函数写上void freeTree(Tree T) { if (T NULL) return; freeTree(T-left); freeTree(T-right); free(T); }每组测试数据读完后基准树释放掉每个候选序列比较完候选树也释放掉。别觉得判题系统内存够就无所谓一旦以后处理更大的数据或者本地反复跑多组样例内存泄漏会被无限放大。我在实际调其他树的题目时就见过因为不释放节点导致内存持续增长最后把本地环境卡到假死的情况。2.4 为什么这个方案不“高级”但能保底建两棵树再比较好处是思路直接、不容易错尤其适合刚学完二叉搜索树的阶段。缺点是多写了一遍建树逻辑还要小心释放。如果面试或考试要求你写得更优雅可以考虑下面这种只建一棵树的做法。3. 少建一棵树的判定法用标记检验插入序列3.1 核心观察祖先必须比后代先插入要判断候选序列能否生成同一棵 BST可以先想清楚一个问题一棵基准树确定后哪些插入序列是合法的答案是每个节点插入时它到根节点路径上的所有祖先节点都必须已经存在。换言之插入顺序必须满足“祖先先于后代”。例如基准树根是 3那么任何合法序列的第一个数字都必须是 3因为第一个插入的数字会成为根。如果第一个数字不是 3这棵树的根就变了后面的讨论都没有意义。再往下看根 3 的左孩子是 1、右孩子是 4那么数字 1 和 4 都必须在各自的子树里早于它们的孩子出现。数字 1 必须早于 2 出现因为 2 是 1 的右孩子。这个“祖先优先级”就是判断的抓手拿着候选序列在基准树上查找当前数字应该落在哪个位置如果查找路径上出现了一个还没有被访问过的节点那么这个候选序列就打乱了祖先顺序必然生成不同的树。3.2 check 函数递归版与迭代版给每个节点加一个 flag表示“在当前候选序列中这个节点是否已经被访问过”。一开始全部 flag 都是 0。对候选序列的每个数字 x在基准树上找 x同时更新 flag。递归版int check(Tree T, int x) { if (T NULL) return 0; if (T-flag) { // 当前节点已经作为祖先出现过了可以继续往下找 if (x T-v) return check(T-left, x); else if (x T-v) return check(T-right, x); else return 0; // 排列约束下不会出现重复访问 } else { // 当前节点还没出现过它必须就是我们要找的数字 if (x T-v) { T-flag 1; return 1; } else { return 0; } } }这个递归函数看起来很短逻辑其实挺绕。我当初第一次看的时候也纠结了很久“为什么走到 flag 为 0 的节点就一定要判断 x 是否等于它”。你可以这样理解如果一个节点 flag 是 0说明在当前候选序列里这个节点还没有被插入。但现在我们要从它身上穿过去找 x相当于 x 的插入位置在它下方。可是在 BST 插入规则里除非这个节点已经存在否则 x 不可能出现在它的子树里。现在它还没被插入x 却要先来说明候选序列违反了祖先优先规则结构必然和基准树不同。如果觉得递归不好理解迭代版更直白int checkIter(Tree T, int x) { Tree p T; while (p ! NULL) { if (p-flag) { if (x p-v) p p-left; else if (x p-v) p p-right; else return 0; } else { if (x p-v) { p-flag 1; return 1; } else { return 0; } } } return 0; }迭代版就是模拟一个指针在树上走遇到已经访问过的节点就决定往左还是往右遇到没访问过的节点就判断它到底是不是 x。3.3 每组序列开始前要重置 flag候选序列不止一个所以在处理每一个新序列前要把基准树上所有节点的 flag 全部清零void resetFlag(Tree T) { if (T NULL) return; resetFlag(T-left); resetFlag(T-right); T-flag 0; }主流程框架int main() { int N, L; while (scanf(%d, N) 1 N ! 0) { scanf(%d, L); Tree T NULL; int x; for (int i 0; i N; i) { scanf(%d, x); T insert(T, x); } while (L--) { resetFlag(T); int wrong 0; for (int i 0; i N; i) { scanf(%d, x); if (!wrong !check(T, x)) { wrong 1; } } puts(wrong ? No : Yes); } freeTree(T); } return 0; }注意if (!wrong !check(T, x))里的!wrong。一旦某个数字检查失败后面的数字就不用再进 check 了但还要继续读数把本行剩下的数字从输入流里读完不能直接 break 出去。3.4 手工走查一轮为什么 3 2 4 1 会失败用刚才的样例手动跑一遍。基准序列 3 1 4 2 生成的树为3 / \ 1 4 \ 2候选序列 3 4 1 2第一个数字 3。根节点 3 的 flag 是 0x 等于 3标记根成功。第二个数字 4。根已经被标记x 大于 3往右走到节点 4。4 的 flag 是 0x 等于 4标记成功。第三个数字 1。从根 3 开始x 小于 3往左走到节点 1。1 的 flag 是 0x 等于 1标记成功。第四个数字 2。从根 3 开始小于 3走到左孩子 1此时 1 的 flag 是 1说明 1 已经出现过可以继续。2 大于 1往右走到节点 2。2 的 flag 是 0x 等于 2标记成功。全部通过输出 Yes。再看候选序列 3 2 4 1。第一个数字 3标记根成功。第二个数字 2从根 3 开始x 小于 3往左走到节点 1。此时节点 1 的 flag 是 0而 x 等于 2不相等。2 不可能跳过节点 1 出现在 1 的右子树里于是 check 返回 0。这是一个非常典型的失败模式候选序列试图把 2 放在比 1 更早的位置但基准树中 2 是 1 的右孩子插入顺序搞反了。3.5 为什么这个判定法能成立每检查完一个数字我们相当于把候选中“已经合法插入的节点”在基准树上做了标记。检查下一个数字时如果它落在已标记节点围成的内部区域说明它的祖先都已经出现顺序合法如果它撞上一个尚未标记的节点只有一个可能这个未标记节点应该是它的祖先但候选序列把它排在后面了。一旦出现这种情况当前这两组插入顺序就不可能生成同一棵树。由于节点值互不相同不存在“撞上了但还能将就”的情况。这个思路也被很多教材称为“标记法”是这道题比较有代表性的标准解法。4. 边界情况与自查清单最容易丢分的地方4.1 N0 与多组测试的输入处理多组数据的题目常见写法是while (scanf(%d, N) 1 N ! 0)。注意先判断 scanf 返回值再判断 N 是不是 0。个别同学写成while (scanf(%d, N) N)如果读入失败会循环不下去但在这里读入失败通常不会发生严谨一点最好检查返回值。读到 N0 时必须直接结束不要再试图读 L更不能去建一棵空树来比较。4.2 check 失败后还要把本行数字读完这是我反复强调的一点。假设当前候选序列已经发现错误代码仍然要把这一行的 N 个整数全部读进来否则后面的测试数据会全部错位。用if (!wrong !check(T, x)) wrong 1;这种写法wrong 变成 1 之后 check 就不会被调用但 scanf 每次都执行正好满足需求。4.3 单节点、链状退化和排列约束的影响N1 时基准树只有一个节点候选序列也只有一个数字。由于两个序列都是 1 到 1 的排列那个数字必然是 1所以输出 Yes。这种情况代码会自动处理但心里要有个底。如果 N 稍微大一点输入序列如果是有序的比如 1 2 3 4会生成一条右链。链状树在递归插入时深度等于 NN 小的时候没问题。这里又体现“排列”约束的重要性节点值从 1 到 N 不重复查找时不会卡在重复值分支上check 的返回值也只需要考虑 0 或 1。4.4 位置数组存树的下标陷阱有人可能觉得节点值正好是 1 到 N能不能不用指针建树而是用一个数组模拟完全二叉树的下标比如根在下标 1左孩子 2v右孩子 2v1这种方案在 N 很小时能跑通但一旦树严重退化比如全部往右挂节点编号可能会接近 2 的 N 次方级别数组根本开不了那么大。这道题 N 不超过 10数组开 1024 还勉强够但这不是一个可扩展的思路也不如链式存储直观。我自己写题时试过一次就果断放弃了还是老老实实建树。4.5 写完后对照这个清单自查每组测试开始前基准树是否重建每组候选序列开始前是否调用 resetFlag基准树是否在每组数据结束后释放候选序列的 N 个数字是否每行都读完Yes/No 的大小写和换行是否正确N0 时是否直接退出没有多余输出这些细节看起来琐碎却是实际扣分最多的位置。5. 从这道题迁移出去同构、镜像与递归设计5.1 “同一棵”是带值的结构一致这道题的比较标准可以理解为“值和结构同时相等”。两个 BST 中序遍历结果相等只能说明它们包含同样的元素序列不能说明结构相同。比如 1 2 3 生成的右链和 2 1 3 生成的平衡小树中序遍历都是 1 2 3但显然不是同一棵树。在做这道题时我特意去对比了另一道经典题“树的同构”。同构题里允许左右子树互换比较函数会多一个分支左子树可以和对方的左子树比也可以和对方的右子树比。判断代码大概是这样int isomorphic(Tree A, Tree B) { if (A NULL B NULL) return 1; if (A NULL || B NULL) return 0; if (A-v ! B-v) return 0; return (isomorphic(A-left, B-left) isomorphic(A-right, B-right)) || (isomorphic(A-left, B-right) isomorphic(A-right, B-left)); }对比一下就能发现“是否同一棵”是更严格的要求左右子树不能互换。5.2 如果题目改成判断镜像对称还有一种常见变体是判断一棵树是否关于根节点镜像对称。递归思路类似但要比较的是一棵树的左子树和另一棵子树的右子树int isMirror(Tree A, Tree B) { if (A NULL B NULL) return 1; if (A NULL || B NULL) return 0; if (A-v ! B-v) return 0; return isMirror(A-left, B-right) isMirror(A-right, B-left); }判断整棵树是否对称时调用isMirror(T-left, T-right)。这个函数同样处理了空指针和值不一致的情况只是左右比较的顺序反过来了。5.3 我写递归比较的一个固定套路做个总结的话我写这类树比较的递归函数习惯先问自己三个问题第一空指针怎么处理大多数情况是把两个都空视为相同一个空视为不同。第二当前节点能不能直接判定失败比如值不相等那就不用递归了直接返回 0。第三剩余结构怎样组合左右都相同或者在某些题目里左右互换也算把递归结果用与或关系串起来。想清楚这三步很多树的判断题都能快速套上。这道“是否同一棵二叉搜索树”的标记法虽然不直接属于这三个问题但它的递归 check 依然遵循同样的模式先处理 flag 状态再决定是进入左子树还是右子树最后根据当前节点值判定成功失败。最后补充一个我实际操作中的习惯。写完代码后不要急着提交先在草稿纸上画一棵基准树然后随便写两个候选序列一个可以生成同一棵树一个生成不了手工走一遍 check 过程。如果手工走查顺畅代码基本不会出问题如果手工走查都很乱那多半是算法理解还差一层。这道题我后来能一次通过靠的正是这个笨办法。