在《数据结构》树这一章的编程练习里“是否同一棵二叉搜索树”算是比较能拦住人的一道题。它不直接给你两棵建好的树而是给你两个插入序列让你判断它们最终能不能生成同一棵二叉搜索树。第一次看到这个题的人很容易被“序列”这两个字绕进去明明 {2,1,3} 和 {2,3,1} 插入顺序不同得到的树却一模一样到底算不算同一棵如果你正在刷树这一章或者准备面试想复习二叉搜索树这篇就把我从题面、三种解法到代码调试的完整过程写出来可以直接参考。1. 题目到底在考什么先看清“同一棵BST”的本质1.1 题面复盘输入输出到底长什么样先把题面讲清楚。每组数据第一行给出两个正整数 N 和 LN 代表每个序列里有多少个数字L 代表后面要检查的序列个数。第二行给出 N 个数字这是“初始插入序列”用来建成一棵二叉搜索树当作基准。接下来有 L 行每行也有 N 个数字每个都是“待检查序列”。我们要对每一个待检查序列回答它和初始序列按顺序插入空树之后能不能得到同一棵二叉搜索树能就输出 Yes不能就输出 No。题目要求循环读入碰到 N0 时整组数据结束。比如输入可能是4 2 3 1 4 2 3 4 1 2 3 2 4 1 0意思是有 4 个节点2 个待检查序列。初始序列是 {3,1,4,2}后面两行分别是待检查序列。输出会是对应两行结果。为了简化问题题目保证每个插入序列都是 1 到 N 的一个排列不用处理重复值的特殊情况。这个 N0 结束的多组输入格式是很多人在考试和上机时丢分的地方。它不是只处理一组数据而是会一直读到文件结束。设计中把 N0 当作终止标记本质上是一个很经典的“循环读入 终止条件”问题放到树题里就要求你对每一组数据都独立建树、独立判断、独立释放内存。1.2 序列不同树为什么会相同为什么插入序列不同生成的树可能一样用最简单的例子来说{2,1,3} 和 {2,3,1}。先插入 {2,1,3}2 成为根1 比 2 小放到左边3 比 2 大放到右边。最终是一棵根为 2、左孩子 1、右孩子 3 的树。再插入 {2,3,1}2 还是根3 比 2 大先放到右边随后插入 1比 2 小放到左边。最后仍然是根为 2、左孩子 1、右孩子 3 的树。两棵树完全一样。核心原因在于 BST 的插入过程有一个特点每个新节点沿查找路径落到空位置路径上经过的节点必须已经存在。只要一个序列中每个节点的所有祖先都出现在它前面最终形成的树结构就不会变。换句话说一棵二叉搜索树一旦确定它对应的“合法插入序列”不止一个所有满足“祖先先于后代出现”这一顺序的序列都会得到同一棵树。反过来一个序列一旦给定插入结果就是唯一的。给定输入序列可以唯一确定一棵 BST。但给定一棵 BST会有多种插入序列可以生成它。这个双向关系正是这道题要考察的核心你不仅要会建树还要能判断两个序列在“插入语义”下是否等价。1.3 “同一棵”指的是 same tree不是 isomorphic判断两棵树是否“同一棵”这里的含义是结构完全一样每个节点上的值也一样。这是 LeetCode 上经典的 Same Tree 问题判定条件是两棵树同时为空或者根节点值相等、左子树相同、右子树相同。有一种容易混淆的概念叫“同构”isomorphic它允许左右子树互换之后仍然算作同一种树。在很多教材的“树的同构”题里左孩子变成右孩子是可以接受的。但二叉搜索树里绝对不能这么看因为左小右大的性质一旦被破坏查找的语义就丢了。所以本题判断的是严格的相同左右子树不能互换。2. 解法思路拆解从“笨办法”到“不建树”2.1 思路一把两棵树都建出来再递归对比最符合直觉的做法就是为每个序列都建一棵二叉搜索树然后递归判断两棵树是否相同。这个方法不需要额外解释“为什么”代码也非常直白。int IsSameTree(BinTree t1, BinTree t2) { if (t1 NULL t2 NULL) return 1; if (t1 NULL || t2 NULL) return 0; if (t1-data ! t2-data) return 0; return IsSameTree(t1-left, t2-left) IsSameTree(t1-right, t2-right); }这个函数同时兼顾了结构和值只要有一边为空另一边不为空说明结构不同返回 0两边的值不一样也返回 0。整棵树递归完都没问题才返回 1。它的缺点也明显每来一个待检查序列就要建一棵新树。假设有 L 个待检查序列每个序列长度是 N最坏情况下建一棵树要 O(N^2) 的时间序列本身退化成递增序列时BST 会退化成长链每次插入都要从头走到尾然后比较还要再花 O(N)。课程题目里 N 通常很小这么写也能过但总感觉绕了一步明明可以只建一次基准树为什么每个序列都要重建一棵2.2 思路二只建一棵树让待检序列在树里“接受检验”这才是这道题的精华解法。我当初学的时候第一次看到这个思路确实有点惊艳。做法是只把初始序列建成一棵二叉搜索树 T。然后对每个待检查序列不建树而是让序列里的数字依次在 T 上做一次“查找”。查找过程中给每个节点加一个 flag 标记0 表示这个节点在这次序列的判断过程中还没被访问过1 表示已经访问过。判断规则只有两条。第一如果当前节点的 flag 为 1说明它是之前某个数字的祖先已经在查找路径上出现过。接下来就按 BST 规则继续向左或向右找。第二如果当前节点的 flag 为 0说明这个节点还没被访问过。如果我要找的数字正好等于当前节点那说明这个节点现在才第一次遇到顺序正常把它标记为 1继续处理后面的数字。如果我要找的数字不等于当前节点说明我在查找某个数字时绕到了一个还没有被访问过的祖先节点上这个序列的插入顺序一定有问题直接判 No。用例子走一遍。初始序列 {3,1,2,4}建出的树是根 3左孩子 11 的右孩子 2右孩子 4。待检查序列是 {3,2,1,4}。数字 3根节点 3 的 flag 是 0当前要找的数字正好等于 3合法把根标记为 1。数字 2根节点 3 的 flag 是 12 小于 3向左走。到左孩子 1发现 1 的 flag 是 0说明 1 在这个序列里还没出现过。但我们现在要找的是 2不是 1于是直接返回 0。为什么这里就错了因为在待检查序列 {3,2,1,4} 中2 出现在 1 之前。如果按这个顺序插入插入 2 时 1 还不在树里2 会直接成为 3 的左孩子之后 1 再插入时只能成为 2 的左孩子。最终树变成根 3、左孩子 2、2 的左孩子 1、右孩子 4和原树不一样。所以输出 No。这个方法的好处是只建一棵树节约内存而且每次判断都像是一棵现成的树在“审问”这个序列。它更贴近 BST 的本质插入顺序的合法性取决于每个节点的祖先是否先于它出现。2.3 思路三不建树直接递归划分序列如果把思路二的本质再抽象一层那就是两个插入序列等价不需要真的建树直接对序列做分治。关键观察是任意一个插入序列第一个元素一定是整棵树的根。序列中所有比根小的数字按原顺序进入左子树所有比根大的数字按原顺序进入右子树。于是两个序列生成同一棵 BST就必须满足三个条件首元素相同左子序列等价右子序列等价。这个递归定义非常干净。用 C 的 vector 写出来很直观bool judge(const vectorint a, const vectorint b) { if (a.empty() b.empty()) return true; if (a.size() ! b.size()) return false; if (a[0] ! b[0]) return false; vectorint aLeft, aRight, bLeft, bRight; for (int i 1; i (int)a.size(); i) { if (a[i] a[0]) aLeft.push_back(a[i]); else aRight.push_back(a[i]); } for (int i 1; i (int)b.size(); i) { if (b[i] b[0]) bLeft.push_back(b[i]); else bRight.push_back(b[i]); } return judge(aLeft, bLeft) judge(aRight, bRight); }依然用 {3,1,2,4} 和 {3,2,1,4} 举例。两个序列首元素都是 3。初始序列分出左子序列 {1,2}、右子序列 {4}。待检查序列分出左子序列 {2,1}、右子序列 {4}。右子序列没问题左子序列递归比较{1,2} 的首元素 1 不等于 {2,1} 的首元素 2直接返回 false。这个思路的代码量最少也不需要设计 flag只要理解“小于根的进左、大于根的进右、相对顺序不变”这一条规律就能写对。面试时如果被问到“两个数组能否生成相同的 BST”我会优先用这个分治解法讲思路。2.4 三种思路的对比与选择为了让你一眼看清差别我把三种方法整理成一张对比表方法是否建树单序列最坏复杂度代码量适用场景分别建树再比较每个序列建一棵建树 O(N^2) 比较 O(N)中初学验证、理解递归比较单棵树 flag 检查只建一棵基准树每次查找 O(N)整体最坏 O(N^2)中课程标准做法内存友好不建树分治比较不建树每次划分扫描 O(N)整体最坏 O(N^2)少面试讲思路、快速实现三种方法在 N 很小的时候性能差距可以忽略。真正的差别在于你是否理解了“序列和树之间的对应关系”。方法一建立树之后比较是纯数据结构操作方法二用 flag 检查祖先顺序开始往 BST 的语义上靠方法三直接把序列递归划分成左右子树序列是纯分治思路。如果能把方法三彻底想明白说明你对 BST 插入过程的理解到了另一个层次。3. 核心代码实现从建树到完整判断3.1 树的节点定义、插入与建树下面给出一个相对完整的 C 语言实现以方法二为主线因为它在课程里最常用也最方便配合 flag 讲解。#include stdio.h #include stdlib.h typedef struct TreeNode *BinTree; struct TreeNode { int data; BinTree left; BinTree right; int flag; // 0 表示本次判断中还没访问过1 表示已经访问过 }; BinTree Insert(BinTree T, int x) { if (T NULL) { T (BinTree)malloc(sizeof(struct TreeNode)); T-data x; T-left T-right NULL; T-flag 0; return T; } if (x T-data) { T-left Insert(T-left, x); } else if (x T-data) { T-right Insert(T-right, x); } // 题目保证是 1~N 的排列不会出现相等分支 return T; }插入逻辑就是标准 BST 插入小于往左大于往右。因为题目保证输入是排列所以不需要考虑相等的情况。如果以后自己扩展题目出现了重复数字就得额外约定“等于时放左边还是右边”树的形态会因此变化判断逻辑也要相应调整。3.2 思路二的判定函数与 flag 重置核心判断函数 check 是这道题的灵魂int check(BinTree T, int x) { if (T NULL) return 0; if (T-flag) { // 当前节点之前已经访问过继续按 BST 规则往下找 if (x T-data) { return check(T-left, x); } else if (x T-data) { return check(T-right, x); } else { return 0; // 出现了重复数字按本题约定判不一致 } } else { // 当前节点还没访问过 if (x T-data) { T-flag 1; return 1; } else { return 0; // 绕过一个未访问节点顺序错误 } } }注意 check 函数里开头加了一个 T NULL 的保护判断。题目保证待检查序列里的数字一定在树中正常不会走到这一步但加上这个保护可以让函数更健壮万一输入数据不合法也不会段错误。每次判断完一个待检查序列必须把树里所有节点的 flag 重置为 0恢复原状再判断下一个序列void ResetFlag(BinTree T) { if (T NULL) return; T-flag 0; ResetFlag(T-left); ResetFlag(T-right); }释放整棵树也要写成递归void FreeTree(BinTree T) { if (T NULL) return; FreeTree(T-left); FreeTree(T-right); free(T); }3.3 思路三的分治判定实现分治方法用 C 写最舒服因为 vector 切子序列非常直接。如果你非要用 C也可以改成传数组下标范围但边界变量会多不少容易写乱。面试或者平时练习我更推荐 C 版本。#include vector using namespace std; bool judge(const vectorint a, const vectorint b) { if (a.empty() b.empty()) return true; if (a.size() ! b.size()) return false; if (a[0] ! b[0]) return false; vectorint aLeft, aRight, bLeft, bRight; for (int i 1; i (int)a.size(); i) { if (a[i] a[0]) aLeft.push_back(a[i]); else aRight.push_back(a[i]); } for (int i 1; i (int)b.size(); i) { if (b[i] b[0]) bLeft.push_back(b[i]); else bRight.push_back(b[i]); } return judge(aLeft, bLeft) judge(aRight, bRight); }很多第一次写分治的人容易漏掉 a[0] ! b[0] 这个判断或者只记得比较左子序列忘了右子序列。这里一定要两个递归同时成立才行因为左子树和右子树都必须一致。3.4 主流程与多组输入处理主流程里最容易出问题的不是树本身而是多组输入的读入方式。int main() { int N, L, x, i, j; while (scanf(%d, N) 1 N) { scanf(%d, L); BinTree T NULL; for (i 0; i N; i) { scanf(%d, x); T Insert(T, x); } for (i 0; i L; i) { int ok 1; for (j 0; j N; j) { scanf(%d, x); if (ok) { ok check(T, x); } // ok 变成 0 后仍然要把当前序列剩余数字读完 } printf(ok ? Yes\n : No\n); ResetFlag(T); } FreeTree(T); } return 0; }这里有一个特别容易踩的坑如果已经判定当前序列是 No后面的数字要不要继续读入必须继续读。因为循环里的 scanf 每次都在消耗输入流里的数字如果不读下一行序列的第一个数字会被当成当前序列的剩余部分整个数据就乱了。所以代码里 ok 变成 0 之后我们只是不再调用 check但仍然把数字逐个 scanf 读掉。另一个需要注意的是 ResetFlag 的位置。它必须在每个待检查序列判断完之后立即执行而不是等所有 L 个序列都判断完再统一重置。否则下一个序列会带着上一个序列的 flag 痕迹前面几个数字可能因为“碰巧已经访问过”而误判通过。4. 常见错误、边界情况与调试技巧4.1 多组输入里 N0 退出的坑最常见的一类错误就是只处理了一组数据。很多人写完发现样例过了提交却错误原因就是没有处理多组输入。正确写法是用 while (scanf(%d, N) 1 N) 把整组逻辑包起来。当读到 0 时直接跳过循环体结束程序。这里还要注意 scanf 的返回值。如果你只写 while (scanf(%d, N))遇到文件末尾时返回值是 EOF也会退出循环但读入失败后再去 scanf(%d, L) 就会有问题。因此用 scanf(%d, N) 1 这种写法更规范保证是在成功读到一个整数后才进入循环。4.2 flag 重置漏掉导致的连锁错误方法二最经典的错误症状是第一组序列判断正确从第二组开始结果全乱。原因是每判断完一个序列后树里一部分节点的 flag 是 1。如果不清零下一个序列在查找时会把这些残留的 1 当成“曾经访问过”的标记本来应该报错的地方可能直接放行。解决方法是保证每个序列判断结束后都调用 ResetFlag(T)并且这个调用是必走的不应放在某个条件分支里。我建议在主流程里先判断、打印、再重置、再进入下一个循环把这个顺序固化下来就不会漏。4.3 分治时子序列切分错误分治方法的边界问题比 flag 更难排查。常见错误有三个。第一判空顺序不对。代码开头必须先判断是否都为空再访问 a[0]。如果 a 为空、b 不为空直接访问 a[0] 就会越界。正确顺序是都空返回 truesize 不同返回 false首元素不同返回 false。第二切分子序列时把根元素也包含进去。很多人循环从 0 开始遍历导致根元素又被分到左或右子序列里递归永远停不下来。必须从下标 1 开始。第三只递归比较了左子序列忘了右子序列。这个错误不会导致崩溃但结果会错得非常隐蔽。写完后建议自己用几个不同例子手动跑一遍。4.4 重复元素到底怎么处理题目保证序列是排列所以没有重复值。但如果你自己扩展练习问如果数字可以重复怎么办这里要先约定插入规则否则无解。通常的习惯是小于当前节点往左大于等于当前节点往右。一旦这样约定重复值会不断往右挂树的形态和“只允许小于向左、大于向右”时不同。check 函数里如果 T-flag 为 1 时遇到 x T-data说明数字重复出现且当前路径下不允许再遇到相同值应该判为不一致。初学阶段不建议过度纠结重复值先把排列版本的逻辑吃透后面再研究泛化情形。4.5 调试技巧把树打印出来看树结构的问题最有效的调试方法就是画图。手画不方便时可以写一个先序遍历打印函数。void PrintPreOrder(BinTree T) { if (T NULL) return; printf(%d , T-data); PrintPreOrder(T-left); PrintPreOrder(T-right); }为什么用先序而不是中序因为 BST 的中序遍历一定是有序递增序列任何两棵包含同样数字的 BST中序序列都一样看不出区别。但先序序列不同两棵相同的 BST先序序列一定相同两棵不同的 BST先序序列几乎不可能相同。实际上一颗 BST 可以由它的先序序列唯一确定所以比较先序序列是最快的调试手段。做题时如果怀疑自己的判断函数写错了就把初始序列和待检查序列分别建树打印两棵树的先序序列肉眼一对比就出结果。这个方法在面试讲题时也很有说服力只要两个插入序列生成的 BST 的先序序列完全相同这两棵树就完全相同。4.6 复杂度分析与面试延伸这道题的 N 一般很小三种方法都能轻松通过。但面试时如果被追问你要能说清楚复杂度无论哪种方法插入建树在最坏情况下都可能退化成 O(N^2)因为序列有序时 BST 会变成长链。check 每个数字都要沿树高查找平均 O(log N)最坏 O(N)所以整个序列判断最坏也是 O(N^2)。你还可以顺势抛出一个更深的概念给定 N 个互异数字能构造出多少棵不同的二叉搜索树答案是卡特兰数。比如 N3 时是 5 棵。这跟本题正好是一对互补视角本题讨论“多棵不同的插入序列对应同一棵树”卡特兰数讨论“N 个节点能产生多少棵结构不同的树”。能把这两个方向串起来讲面试官通常会认为你对 BST 的理解不是死记硬背。这道题刷完我的建议是不要满足于“把题过了”。试试把方法二改成方法三重新写一遍再想想如果序列里允许重复怎么改最后再看看卡特兰数相关的问题。这样一轮下来树这一章最核心的“递归、分治、二叉树性质”基本就吃透了。我当时花了一下午反复在这几种解法之间切换后来的二叉树面试题基本没再慌过。