04-树4 是否同一棵二叉搜索树从一道经典题看树的比较逻辑很多学数据结构的朋友一看到“二叉搜索树”这几个字第一反应就是“基础操作”插入、删除、查找最多再加一个中序遍历。考试考来考去也就这些面试问来问去也绕不开这些。但当我真正动手去做“是否同一棵二叉搜索树”这道题时才发现事情没那么简单——它表面上考的是树的遍历和比较实际上考的是你对二叉搜索树结构本质的理解程度。这道题是很多高校《数据结构》课程里树这一章的经典实验题网上的常见版本是给定一组数字的插入序列两棵二叉搜索树如果长得完全一样则认为它们是同一棵树。问题是输入序列可能不同但生成的树却可能相同你怎么判断这个问题的核心不只是“写一个递归函数”而是想清楚“什么才算同一棵树”以及“怎样比较才高效”。这篇文章我打算从问题本身出发把二叉搜索树的构建、树的比较方法、代码实现以及实际调试过程中踩过的坑一次性讲透适合正在复习数据结构期末考试的本科生也适合准备算法面试的求职者甚至对写过一段时间代码但没系统性学过树结构的开发者同样有参考价值。1. 判断同一棵二叉搜索树的思路拆解1.1 问题的本质不是比序列而是比结构先还原一下题目的典型场景。假设输入序列是5 6 3 4 2你按这个顺序插入一棵空树会得到一棵特定的二叉搜索树。另一个人给你的序列是5 3 6 2 4按同样的插入规则得到的树看起来可能一模一样。实际上这两棵树的形态是相同的只是插入顺序不同。反过来如果序列是5 6 3 4 2和5 6 3 4 2那显然一样。但更微妙的是某些序列虽然元素相同、顺序不同生成的树却完全不一样。所以这道题的核心是判断“两棵二叉搜索树的形态是否完全相同”也就是结构一致、对应节点的值也一致。序列不是判断标准树本身才是。这就引出了第一个关键点你用什么方式去描述一棵树不同描述方式决定了比较的复杂度。常见方案有三种递归同步遍历、序列化比较、构造唯一序列再比较。三种各有优缺点我后面逐一展开。1.2 二叉搜索树的插入规则决定了树的形态再往下想一层为什么同样的元素插入顺序不同会导致树的形态不同这就要回到二叉搜索树的插入逻辑从根节点开始比较。如果待插入值比当前节点小就往左子树走。如果比当前节点大就往右子树走。直到走到空位置插入新节点。这个过程里树的形态完全由“每个元素在插入那一刻的相对顺序”决定。比如5 3 4和5 4 3第一棵树的 3 是 5 的左孩子4 是 3 的右孩子第二棵树的 4 是 5 的左孩子3 是 4 的左孩子。形态完全不同。所以判断两棵树是否相同是在判断结构而不是判断插入过程。这点想通了代码就好写了。2. 三种判断思路的原理与选型2.1 递归同步遍历最直接也最稳妥第一种方法也是最容易想到的两棵树同时从根节点开始比较。如果两个根节点都为 null说明这一层一致如果其中一个为 null 另一个不为 null说明不一致如果两个都不为 null则先比较值再递归比较各自的左子树和右子树。这个方法的本质是“同步前序遍历”。前序遍历的顺序是根、左、右你从根开始逐层对比任何一步不一致就可以提前停止。时间复杂度是 O(n)n 是节点数空间复杂度是递归栈的深度最坏情况是树退化成链表深度为 n平均情况下是 O(log n)。实际写代码的时候这个方案是最不容易出错的因为它直观地映射了我们比较两棵树时的自然思维过程。而且一旦发现某处不匹配能立刻返回 false不用构建完整序列再比这在树比较大的时候能省不少时间。2.2 序列化比较把树变成字符串再比第二种思路有点取巧把一棵树“拍平”成一个字符串然后比较两个字符串。这里的核心问题是选什么遍历方式才能唯一确定一棵树如果只用中序遍历那对二叉搜索树来说是“左根右”结果是升序序列。比如序列5 3 4、5 4 3这两棵不同形态的树中序遍历结果都是3 4 5一模一样。所以中序遍历不能唯一表示一棵树必须配合其他遍历方式。常见做法是用前序遍历并在遇到空节点时补充特殊标记比如#。比如上面说的5 3 4前序遍历加空标记是5 3 # 4 # # #而5 4 3是5 4 3 # # # #。两个字符串完全不同能区分形态。这个方法的优点是代码简洁尤其是你已经有现成的树序列化工具时逻辑上减少了很多递归比较的细节。缺点是要生成完整字符串即便两棵树在第一层就不一致也要先序列化完才能比较时间和空间上都有额外开销。另外注意避免把空标记与数值混淆比如节点值本身可能是#或包含分隔符需要考虑协议设计。2.3 两次遍历取序列再比较处理非空标记的替代方案如果不想在序列化时加入空标记也可以用“前序 中序”的双序列方案。原理是一棵二叉树若已知前序遍历序列和中序遍历序列可以唯一确定这棵二叉树。二叉搜索树也满足这个性质因此分别取两棵树的前序和中序序列对比这两个序列对是否完全一致即可。这种方法在理论上很可靠实现也不算复杂。但要小心一个细节序列的生成过程必须在同一套遍历函数下完成否则根顺序对不上。另外中序序列在二叉搜索树场景下永远是升序的所以你其实只需要比较前序序列再验证中序序列都是同一组元素的升序排列。这相当于进一步简化成了一个“前序序列唯一 元素集合相同”的判断。不过真实考试和面试里很少要求这种间接方法因为直接递归已经足够清晰。我提它主要是为了帮你理解树的序列化表示的重要性这在后续做“二叉树重建”“二叉树的序列化与反序列化”等题目时会用到。2.4 方法对比总表方法时间复杂度空间复杂度实现难度适用场景递归同步遍历O(n)O(h)h 为树高低最推荐面试常用序列化字符串比较O(n)O(n)中已有序列化工具或在线评测环境前序中序双序列比较O(n)O(n)中学习树重建时辅助理解我在实际做题时首选递归同步遍历。它最贴近问题的数学本质代码量少不容易出现序列化协议的边界问题。3. 核心代码实现与逐段解析3.1 定义树节点结构无论用哪种语言第一步都是定义节点。这里我用 C 语言来演示因为这正是这门课最常见的要求——陈越、何钦铭主编的《数据结构》教材中树这一章大量使用 C 和 C 风格代码。typedef struct TreeNode *Tree; struct TreeNode { int v; Tree Left, Right; int flag; // 在判同问题中可以用也可以不用 };这个结构体本身很简单但注意我在里面预留了一个flag字段。有些教材版本的“是否同一棵二叉搜索树”问题不是给两棵现成的树而是给一个序列和若干待测序列要求判断哪些待测序列与给定序列生成的树相同。这时候需要先在给定序列上建一棵“标准树”然后把待测序列里的每个数依次到标准树里“搜索”每找到一次就标记这个节点最后检查是否所有节点都被标记。flag就是为这种思路准备的。不过我们这篇文章聚焦的是“给定两棵已经构建好的树”所以flag不是必需的先提一下避免你看到其他版本的代码时产生困惑。3.2 构建一棵二叉搜索树构建过程就是不断调用插入函数。插入函数本身也是一个递归结构代码逻辑不复杂但容易在小细节上出错比如忘记分配内存或者当树为空时没把新节点赋给根指针。Tree NewNode(int v) { Tree T (Tree)malloc(sizeof(struct TreeNode)); T-v v; T-Left T-Right NULL; T-flag 0; return T; } Tree Insert(Tree T, int v) { if (!T) { T NewNode(v); } else { if (v T-v) T-Left Insert(T-Left, v); else if (v T-v) T-Right Insert(T-Right, v); // 等于时不处理因为题目通常保证没有重复元素 } return T; }特别注意NewNode里要显式把Left、Right都置为 NULL。很多初学者漏了这一步结果导致插入时判断!T永远为假或者遍历时直接访问了野指针。这种错误在本地运行可能碰巧不出问题但在线评测系统会直接报段错误Segmentation fault排查起来费时间。另外还有一个易错点插入函数返回值。因为 C 语言里没有引用传递除非用指针的指针所以这里用了“返回新的根节点”的方式调用时写T Insert(T, v)。如果不接收返回值树就会在第一次递归时丢掉新插入的节点。3.3 递归判断两棵树是否相同核心判断逻辑很简洁我把它做成一个独立的函数int IsSameTree(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 IsSameTree(A-Left, B-Left) IsSameTree(A-Right, B-Right); }这段代码一共分四层判断两个节点都为空说明这棵子树已经比完了两边在这一段都没有更多分支返回真。一个为空一个不为空说明结构不对称返回假。两个节点都不为空但值不同直接返回假。两个节点值相同递归比较左子树和右子树。A NULL B NULL这一行是递归的终止条件也是最容易漏掉的一行。如果没有这个终止条件递归调用会在树的底部不断访问A-Left或B-Left而这时 A 或 B 已经是 NULL直接解引用就会崩溃。这条递归思路正是“同步遍历”的典型代表。你把两棵树想象成两个正在对齐的队伍每一步都要检查当前站位是否相同同时一起往下走。一旦有人站错了整个队列就不用再比了。3.4 主函数与输入处理一道完整的题目自然需要主函数来串联。假设题目要求每组数据第一行是序列长度 N 和待比较序列数量 L接下来一行是标准序列后面 L 行是待测序列每组判断后输出 “Yes” 或 “No”。int main() { int N, L; while (scanf(%d, N) N ! 0) { scanf(%d, L); Tree T NULL; int v; for (int i 0; i N; i) { scanf(%d, v); T Insert(T, v); } for (int i 0; i L; i) { Tree T2 NULL; for (int j 0; j N; j) { scanf(%d, v); T2 Insert(T2, v); } if (IsSameTree(T, T2)) { printf(Yes\n); } else { printf(No\n); } FreeTree(T2); } FreeTree(T); } return 0; }这里有几个工程上很重要的细节每组测试数据结束后必须释放 T2 和 T 的内存。虽然很多在线评测不检查内存泄漏但在本地做实验或者在公司面试手写代码时良好的内存管理习惯会加分。标准树 T 只建一次但要在内层循环里反复使用所以不能在内层被释放。我把 FreeTree(T) 放在了外层循环的末尾。输入用while (scanf(%d, N) N ! 0)来循环读入多组数据每组输出独立结果这样符合常见的在线评测输入格式要求。FreeTree是个递归函数也很容易写void FreeTree(Tree T) { if (T) { FreeTree(T-Left); FreeTree(T-Right); free(T); } }这里有另一个小坑要先把左右子树释放完最后才释放当前节点。顺序反了的话当前节点被 free 后访问T-Left就是访问已释放的内存属于未定义行为。4. 从暴力比较到高效搜索教材版的另一种解法4.1 为什么要重新审视题意很多教材和网课版本里“是否同一棵二叉搜索树”这道题并不是纯粹比较两棵已经建好的树而是“给定一个插入序列判断其他若干插入序列是否与其生成同一棵二叉搜索树”。此时如果每给一个序列就完整建一棵树再递归比较代码写起来倒也简单但效率并不理想总时间复杂度是 O(L * N log N)其中 L 是待测序列数量N 是节点数。如果 N 达到几万、L 达到几百这个复杂度会非常难看。更好的解法是先把标准序列建一棵树然后把待测序列中的每个数字在这个树上“搜索”一遍搜索路径上经过的每一个节点都应该依次被访问到。如果有某个节点在搜索时还没有被访问过就说明待测序列不可能是同一棵树。这个方法的巧妙之处在于它利用了二叉搜索树的性质——插入顺序决定路径两棵树相同意味着所有元素的插入路径也相同或者说每个元素在搜索时经过的中间节点集合完全相同。4.2 基于 flag 标记的搜索判断这个思路在代码里体现为“边搜索边标记”。具体做法是给每个节点加一个flag字段初始为 0。对于待测序列中的每个数 x沿着标准树 T 搜索如果当前节点T的flag是 0说明它在之前搜索中没有被访问过那这次路径中访问它是首次符合要求继续向下搜索。如果当前节点T的flag是 1说明这个节点在更早的搜索中已经被访问过而现在又要经过它。这时如果 x 和T-v相等说明这个元素就是当前节点那没有问题如果 x 小于T-v应该去左子树但左子树还没有被访问过因为当前节点之前 flag 为 1 时说明上一次搜索结束时路径已经走完左子树可能已经被访问过或不存在这时就产生了矛盾。其实这个逻辑说起来比较绕我更习惯用一个更简单的等价判断把待测序列中的每个元素在标准树 T 上执行一次“查找”操作查找过程中每经过一个节点就检查该节点是否已经被标记过。如果遇到一个还没标记过的节点但查找的数值又和当前节点不相等说明这个元素不可能属于这棵树的搜索路径立即返回 false。查找完成后把路径上所有未标记的节点标记为 1。当处理完待测序列中所有元素后如果每步都通过说明这棵树和标准树同构。这里的关键在于二叉搜索树的查找路径实际就是插入路径。如果两个序列生成的树相同那么对于任意元素 x在第一棵树中从根到 x 的路径节点集合和第二棵树中从根到 x 的路径节点集合应该完全一致。这比直接递归比较整棵树计算上往往更高效因为不需要为每一个待测序列构建完整的树。4.3 两种解法如何选择站在现在的角度看我更推荐先掌握递归同步遍历的解法因为这是最通用的思维不只是二叉搜索树任意两棵二叉树是否相同的比较都是用这个模板改一改。搜索加标记的方案理论上有它的独特价值尤其当需要大量判断“同一个标准树对应的多个候选序列”时效率优势明显还能让你深入理解搜索树的路径特性。但日常考试和面试里给出的 N 通常不大L 也不会很大两种方式都能 AC。我建议你在本机把两种都实现一遍体会它们在代码量和执行效率上的差异这对理解树结构非常有帮助。5. 实际调试中的常见问题与避坑指南5.1 空指针和野指针的排查思路递归代码里空指针是最常见的崩溃来源。IsSameTree中的四处判断每一处都不是多余的。等你写多了就会发现树的递归遍历有一个通用的防御性写法永远先判断当前节点是否为 NULL再判断它的值。在排查时可以用一个极小的用例做试验比如只有两个节点2 1和2 1。如果程序在递归到左子树后崩溃多半是某个递归分支里没处理NULL情况。不要上来就在大数据集上调试那会浪费时间。5.2 输入输出格式的细节在线评测系统对输出格式要求严格多一个空格、少一个空行都可能导致 Presentation Error虽然不扣分但影响体验。输出 “Yes” 和 “No” 时注意大小写。题目里如果要求每个结果占一行那最后一个结果后面也最好有换行。另外循环输入的条件一定要写清楚。我见过很多同学把while (scanf(%d, N) N ! 0)写成while (N ! 0 scanf(%d, N))这样第一轮 N 是未初始化的值可能会导致不会进入循环或者无限循环。正确顺序是先把 N 读进来再判断 N 是否为 0。5.3 递归深度和性能问题如果二叉搜索树极端不平衡比如退化成一条链递归深度可能达到 N。这时IsSameTree的空间复杂度会退化为 O(N)如果 N 很大可能会爆栈。遇到这种情况可以改成迭代写法用显式的栈来模拟递归。不过在普通课程作业中N 一般不会超过几千递归完全够用。如果你在面试环境中遇到这种题可以用迭代做法展示你考虑到栈溢出的风险。5.4 测试用例构造策略我自己调试这类题目时会准备几组典型的用例完全相同的树5 3 8 2 4对5 3 8 2 4期望输出 Yes。根节点相同但左子树不同5 3 8对5 4 8期望输出 No。节点数相同但结构不同5 3 4对5 4 3期望输出 No。空树和空树期望输出 Yes。一棵空树、一棵非空树期望输出 No。这几组用例能在几分钟内验证你的递归逻辑是否正确比一上来就测试随机大数据集高效得多。6. 这道题背后二叉搜索树在面试和工程中的延伸6.1 面试官到底想考察什么很多求职者以为这道题只是“遍历比较”其实它背后至少涉及三个核心能力理解递归结构树的定义本身就是递归的判断树是否相同必须用递归思维。分析边界条件NULL 的判断、递归终止条件这些是面试官容易深挖的点。时间和空间复杂度分析能说出 O(n) 时间和 O(h) 空间并解释为什么退化成链表时会变成 O(n)。面试官如果再追问一句“如果节点数特别多递归可能爆栈你怎么改成迭代”这时候你是不是能立刻答出用两个栈分别遍历两棵树同步比较这个追问并不难但很多没有实际动手写过的人会卡住。6.2 二叉搜索树的真实工程应用二叉搜索树本身在工程里直接使用的场景不多因为普通 BST 在有序插入时会退化为链表性能变得不可控。所以我们看到更多是它的进阶版本红黑树、AVL 树、B 树和 B 树。比如 Java 的 TreeMap 和 TreeSet 底层就是红黑树C 的 std::map 和 std::set 底层通常也是红黑树。数据库索引常用 B 树。这些结构都能看作是二叉搜索树思想的延伸。因此你熟练掌握了 BST 的插入、查找、删除、遍历之后再去接触这些进阶数据结构会快很多。如果结合最近的热词比如“红黑树”和“B 树”频繁出现在面试题里你就能理解这道“是否同一棵二叉搜索树”解决的问题实际上是树结构比较的基础能力。未来做 AST抽象语法树比较、JSON 树结构比较、目录树同步等场景都会用到同样的递归比较法。6.3 把问题泛化的思考方式掌握这道题之后你可以顺手做几道变形题判断两棵二叉树是否相同不限于二叉搜索树。判断一棵树是否是另一棵树的子树。判断一棵二叉搜索树是否合法即中序遍历是否有序。判断两棵二叉搜索树是否同构允许左右子树的镜像交换也被视为同构。这些题在力扣上都有对应的原题核心思路都绕不开“遍历比较结构”这条主线。一旦你养成“从结构出发”而不是“从序列出发”的思考习惯很多题都会迎刃而解。7. 一份可以直接跑通的完整代码示例为了让你少走弯路我贴一份可以直接运行的完整 C 语言版本使用了递归同步遍历。这份代码我在本地调试过测试了多组数据包括空树、单节点树、退化成链表的情况均能正确输出。#include stdio.h #include stdlib.h typedef struct TreeNode *Tree; struct TreeNode { int v; Tree Left; Tree Right; }; Tree NewNode(int v) { Tree T (Tree)malloc(sizeof(struct TreeNode)); T-v v; T-Left NULL; T-Right NULL; return T; } Tree Insert(Tree T, int v) { if (!T) { T NewNode(v); } else if (v T-v) { T-Left Insert(T-Left, v); } else if (v T-v) { T-Right Insert(T-Right, v); } return T; } int IsSameTree(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 IsSameTree(A-Left, B-Left) IsSameTree(A-Right, B-Right); } void FreeTree(Tree T) { if (T) { FreeTree(T-Left); FreeTree(T-Right); free(T); } } int main() { int N, L; while (scanf(%d, N) N ! 0) { scanf(%d, L); Tree T NULL; for (int i 0; i N; i) { int v; scanf(%d, v); T Insert(T, v); } for (int i 0; i L; i) { Tree T2 NULL; for (int j 0; j N; j) { int v; scanf(%d, v); T2 Insert(T2, v); } if (IsSameTree(T, T2)) { printf(Yes\n); } else { printf(No\n); } FreeTree(T2); } FreeTree(T); } return 0; }注意这份代码假设输入元素没有重复因为教材版通常都这样约定。如果存在重复元素二叉搜索树的插入策略就需要额外定义比如相等时放左子树还是右子树判断逻辑也要对应调整。我个人在实际编写和调试这道题时感受最深的一点是树的题目代码往往不长但很容易在边界条件和内存上出问题。写完以后我建议你专门拿一组“一棵空树、一棵非空树”的用例去测一下递归终止条件拿一组“左子树全空”的用例去测右子树的遍历路径。把这几类边界情况想明白整棵树的理解都会上一个台阶。