企业官网建设流程全解析

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 方法对比总表

我在实际做题时，首选递归同步遍历。它最贴近问题的数学本质，代码量少，不容易出现序列化协议的边界问题。

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); }

这段代码一共分四层判断：

1. 两个节点都为空，说明这棵子树已经比完了，两边在这一段都没有更多分支，返回真。
2. 一个为空一个不为空，说明结构不对称，返回假。
3. 两个节点都不为空，但值不同，直接返回假。
4. 两个节点值相同，递归比较左子树和右子树。

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; }

注意，这份代码假设输入元素没有重复，因为教材版通常都这样约定。如果存在重复元素，二叉搜索树的插入策略就需要额外定义（比如相等时放左子树还是右子树），判断逻辑也要对应调整。

我个人在实际编写和调试这道题时感受最深的一点是：树的题目，代码往往不长，但很容易在边界条件和内存上出问题。写完以后我建议你专门拿一组“一棵空树、一棵非空树”的用例去测一下递归终止条件，拿一组“左子树全空”的用例去测右子树的遍历路径。把这几类边界情况想明白，整棵树的理解都会上一个台阶。