数据结构｜二叉树专题（一）：从递归判断到子树匹配与遍历建树

写在前面

前面的「数据结构——二叉树」系列主要围绕二叉树本身的结构和基础接口展开。从三种递归遍历开始，我们已经陆续实现了结点数量、叶子结点数量、树的高度、第 K 层结点数量、层序遍历、结点查找、二叉树销毁、前序序列建树等接口，帮助我们逐渐熟悉二叉树最基本的递归模型。

但真正开始做题以后会发现：知道「二叉树要用递归」和真正能够写对递归，还是两件不同的事情。

尤其是这些问题：

• 递归函数到底代表什么；
• 什么时候返回 true，什么时候返回 false；
• 左右子树的结果该用&&还是||；
• 递归函数返回的结果是否被正确接住；
• 同时递归两棵树时，两个参数到底应该怎样变化；
• 力扣要求返回动态数组时，应该如何组织结果。

这些问题都需要通过具体题目才能真正掌握。因此从本篇开始进入二叉树专题练习。

本篇按照以下路线逐步展开：

1. 单值二叉树
2. 100. 相同的树
3. 572. 另一棵树的子树
4. 144. 二叉树的前序遍历
5. TSINGK110 二叉树遍历

前几题逐步深化递归判断逻辑，最后进入遍历结果保存与前序序列建树。

一、LeetCode 965：单值二叉树

1.1 题目

如果二叉树每个结点都具有相同的值，那么这棵树就是单值二叉树。只有给定的树是单值二叉树时返回true，否则返回false。

1.2 递归函数的定义

对于当前结点root，我们需要保证：

• 左孩子的值和 root 相同
• 右孩子的值和 root 相同
• 左子树本身也是单值树
• 右子树本身也是单值树

因此递归函数isUnivalTree(root)可以定义为：

判断以 root 为根的整棵树是不是单值二叉树。

1.3 递归终止与逐层判断

终止条件：空树视为合法如果root == NULL，空树本身不会产生不同值，满足单值要求：

if (root == NULL)
{
    return true;
}

当前层校验：左右孩子值匹配左孩子存在时，比较值是否相等，不等则直接返回 false：

if (root->left && root->left->val != root->val)
{
    return false;
}

右孩子同理：

if (root->right && root->right->val != root->val)
{
    return false;
}

这里先判断root->left是为了避免空指针解引用root->left->val。

1.4 左右子树必须同时成立

当前层检查没有问题以后，继续递归校验子树：

return isUnivalTree(root->left)
    && isUnivalTree(root->right);

这里必须用&&，原因很直接：

左子树是单值树并且右子树也是单值树，整棵树才是单值树。

1.5 完整代码

bool isUnivalTree(struct TreeNode* root)
{
    if (root == NULL)
    {
        return true;
    }

    if (root->left && root->left->val != root->val)
    {
        return false;
    }

    if (root->right && root->right->val != root->val)
    {
        return false;
    }

    return isUnivalTree(root->left)
        && isUnivalTree(root->right);
}

1.6 题后总结

这道题第一次非常清晰地体现了二叉树递归的经典结构：

当前层条件 + 左子树结果 + 右子树结果

也就是：当前结点合法 && 左子树合法 && 右子树合法

做二叉树递归题时，首先要想清楚：左右两棵子树之间到底是什么关系？

这道题的答案是「必须同时满足」，所以使用&&。这个思想马上会在下一道题中再次出现。

二、LeetCode 100：相同的树

2.1 题目

给出两棵二叉树p和q，如果两棵树结构完全相同，且对应位置的结点值全部相同，就认为两棵树相同。

2.2 双树同步递归的思路

定义递归函数isSameTree(p, q)：

判断以 p 和 q 为根的两棵二叉树是否完全相同。

和上一题不同，这里需要同时观察两个结点，两棵树同步向下递归。

2.3 三种边界情况

情况1：两个结点都为空

if (p == NULL && q == NULL)
{
    return true;
}

两个位置结构一致，返回 true。

情况2：一个为空，一个不为空

if (p == NULL || q == NULL)
{
    return false;
}

注意这里是在已经排除「两者都为空」之后判断，只要有一个为空，就说明结构不一样。

情况3：值不同两个结点都存在时，比较值：

if (p->val != q->val)
{
    return false;
}

结构位置一致但值不同，仍然不是相同的树。

2.4 左右子树必须同时相同

当前根结点相同还不够，还必须保证：

• p 的左子树 == q 的左子树
• p 的右子树 == q 的右子树

因此：

return isSameTree(p->left, q->left)
    && isSameTree(p->right, q->right);

这里再次出现了和上一题类似的A && B结构。

2.5 完整代码

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    if (p == NULL && q == NULL)
    {
        return true;
    }

    if (p == NULL || q == NULL)
    {
        return false;
    }

    if (p->val != q->val)
    {
        return false;
    }

    // 左子树相同，并且右子树相同，两棵树才真正相同
    return isSameTree(p->left, q->left)
        && isSameTree(p->right, q->right);
}

2.6 题后总结

回头对比单值二叉树和相同的树：

• 单值二叉树：return isUnivalTree(root->left) && isUnivalTree(root->right);
• 相同的树：return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);

写法不同，但思维模式完全一致：

当前层满足要求以后，整棵树是否满足条件，由左右子树共同决定。

也正是完成「相同的树」以后，下一题「另一棵树的子树」就自然出现了。

三、LeetCode 572：另一棵树的子树

3.1 题目

给出两棵树root和subRoot，判断 root 中是否存在某一个结点，使以这个结点为根的整棵子树与 subRoot 完全相同。

3.2 两层递归的拆解

这道题实际上包含两个问题：

1. 两棵树是否相同？—— 这正是刚刚写完的isSameTree
2. root 的哪个位置可能和 subRoot 相同？—— 遍历 root 的所有结点

因此 572 很适合直接复用 100 的代码，形成「外层遍历 + 内层匹配」的两层递归。

站在当前 root 位置上：

• 先判断isSameTree(root, subRoot)，如果相同，直接返回 true；
• 如果当前位置不匹配，那么还有两个可能：subRoot 出现在 root 的左子树中，或者出现在右子树中。
• 只要其中一个存在即可，因此用||连接。

return isSubtree(root->left, subRoot)
    || isSubtree(root->right, subRoot);

3.3 完整代码

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    if (p == NULL && q == NULL)
    {
        return true;
    }

    if (p == NULL || q == NULL)
    {
        return false;
    }

    if (p->val != q->val)
    {
        return false;
    }

    return isSameTree(p->left, q->left)
        && isSameTree(p->right, q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if (root == NULL)
    {
        return false;
    }

    // 先判断以当前 root 为根的树是否和 subRoot 相同
    if (isSameTree(root, subRoot))
    {
        return true;
    }

    // 当前位置不相同，再去 root 的左右子树寻找
    return isSubtree(root->left, subRoot)
        || isSubtree(root->right, subRoot);
}

3.4 典型错误复盘

我第一次写这道题时，写出了下面这种结构，踩了三个非常典型的递归坑：

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if (root == NULL && subRoot == NULL)
    {
        return true;
    }

    if (isSameTree(root, subRoot) == true)
    {
        return true;
    }

    isSubtree(root->left, subRoot->left);
    isSubtree(root->right, subRoot->right);
}

错误一：递归返回值直接丢掉

只写isSubtree(root->left, subRoot->left)，虽然调用了递归，但返回结果完全没有处理。

假设左子树深处真的找到匹配返回 true，回到当前层以后既没有 return 也没有保存，这个 true 直接被丢掉了。

递归不是「调用一下就行」。真正重要的是：下层递归计算出来的结果，上一层到底如何使用。

错误二：函数最后没有 return

函数声明是bool isSubtree(...)，意味着所有执行路径最终都应该返回 true 或者 false。

原代码最后两行调用完递归直接结束，没有 return。在 C 语言中，这会导致未定义行为，得到的结果完全不可靠。

错误三：subRoot 不应该跟着移动

原代码写了isSubtree(root->left, subRoot->left)，这是逻辑上的根本错误。

我们要做的事情是：在 root 的不同位置寻找完整的 subRoot。所以每换一个候选位置，root 可以变，但匹配的目标 subRoot 必须始终保持不变。

正确写法：isSubtree(root->left, subRoot)，而不是subRoot->left。

3.5 题后总结：&& 与 || 的选择

• isSameTree：return 左边相同 && 右边相同;—— 两边都必须满足。
• isSubtree：return 左边找到 || 右边找到;—— 只需要一个位置能够找到即可。

做递归题时，不应该机械记忆「二叉树最后都写左右递归」，真正应该问自己：

左右子问题之间到底是「并且」还是「或者」？

四、LeetCode 144：二叉树的前序遍历

4.1 题目要求：从打印到返回数组

LeetCode 144 要求返回二叉树的前序遍历（根 → 左 → 右）。

如果只是本地打印，我们可以直接写printf("%d ", root->val);。但力扣接口要求：

int* preorderTraversal(struct TreeNode* root, int* returnSize)

也就是说需要：

1. 动态申请一个数组；
2. 把前序遍历结果写进去；
3. 通过returnSize告诉力扣数组中有几个有效元素；
4. 返回数组首地址。

相比本地打印，多了一步「结果保存」的工作。

4.2 思路：先统计结点数，再递归填充

我们已经实现过二叉树结点总数统计，这里直接复用：

int TreeSize(struct TreeNode* root)
{
    if (root == NULL)
        return 0;

    return 1
        + TreeSize(root->left)
        + TreeSize(root->right);
}

流程：

1. 先通过TreeSize得到整棵树的结点数，赋值给*returnSize；
2. 根据结点数 malloc 刚好大小的数组；
3. 定义下标变量，递归遍历数组，把值依次填入。

递归函数BinaryTreePrevOrder(root, arr, pi)的含义是：

将以 root 为根的二叉树前序遍历结果，从数组 arr 的*pi位置开始写入。

4.3 完整代码

// 统计结点数量
int TreeSize(struct TreeNode* root)
{
    if (root == NULL)
        return 0;

    return 1
        + TreeSize(root->left)
        + TreeSize(root->right);
}

void BinaryTreePrevOrder(
    struct TreeNode* root,
    int* arr,
    int* pi)
{
    if (root == NULL)
        return;

    arr[(*pi)++] = root->val;

    BinaryTreePrevOrder(root->left, arr, pi);
    BinaryTreePrevOrder(root->right, arr, pi);
}

int* preorderTraversal(
    struct TreeNode* root,
    int* returnSize)
{
    *returnSize = TreeSize(root);

    int* arr = (int*)malloc(sizeof(int) * (*returnSize));

    int i = 0;
    BinaryTreePrevOrder(root, arr, &i);

    return arr;
}

4.4 避坑指南

为什么不用全局数组？

一开始容易想到int num[100];然后直接往里写，但这种写法不适合力扣提交：

1. 多组测试会复用全局数据：全局变量生命周期覆盖整个程序，如果没有每次重置，上一组测试数据会残留下来。
2. 固定大小不安全：固定 100 个结点，一旦测试数据超过就会数组越界。

更合理的方式永远是：先统计数量 → 按实际数量 malloc → 递归填充。

指针运算符优先级问题

这道题还有一个特别容易写错的表达式：*returnSize++。

如果想表达「returnSize 指向的整数加 1」，这么写是错的。因为后缀++优先级高于*，所以：

*returnSize++  等价于  *(returnSize++)

也就是说，不是数值加一，而是让 returnSize 这个指针自己向后移动了。

真正想让指向的整数自增，应该写：

(*returnSize)++;

括号不能省。写复杂指针表达式时，宁可多加一层括号，也不要凭感觉判断。

五、TSINGK110：二叉树遍历（前序建树 + 中序输出）

5.1 题目

不再给出已经建立好的struct TreeNode*，而是直接给出一串前序遍历字符串，#表示空结点。要求：

1. 根据字符串创建二叉树；
2. 对建立好的二叉树进行中序遍历并输出。

示例输入：abc##de#g##f###示例输出：c b e g d f a

5.2 逆向思路：从序列还原树

之前我们解决的是「树 → 前序遍历 → 序列」，而现在反过来了：

前序序列 → 构建二叉树 → 中序遍历

这是第一次真正利用递归创建树结构，而不仅仅是读取树。

递归函数CreateTree(str, pi)的含义是：

从str[*pi]开始，根据前序序列建立一棵树，并返回这棵树的根结点。

遇到 # 返回空树如果当前字符是#，说明这里是空树，下标后移一位，返回 NULL：

if (str[*pi] == '#')
{
    (*pi)++;
    return NULL;
}

注意：即使遇到 #，也必须让下标向后走一位，否则递归返回以后还是会继续读取同一个 #。

非空结点的处理如果不是 #，创建当前结点，下标后移，然后按照前序「根 → 左 → 右」的顺序递归构建左右子树：

BTNode* root = BuyBTNode(str[*pi]);
(*pi)++;

root->left = CreateTree(str, pi);
root->right = CreateTree(str, pi);

return root;

5.3 完整代码

#include <stdio.h>
#include <stdlib.h>

typedef char BTDataType;

typedef struct BinaryTreeNode
{
    BTDataType data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
} BTNode;

// 创建结点
BTNode* BuyBTNode(BTDataType val)
{
    BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
    if (newNode == NULL)
    {
        perror("malloc");
        exit(-1);
    }
    newNode->data = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 先序字符串构建二叉树
// pi 为下标指针，# 代表空结点
BTNode* CreateTree(char* str, int* pi)
{
    if (str[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }

    BTNode* root = BuyBTNode(str[*pi]);
    (*pi)++;

    root->left = CreateTree(str, pi);
    root->right = CreateTree(str, pi);

    return root;
}

// 中序遍历
void InOrder(BTNode* root)
{
    if (root == NULL)
        return;

    InOrder(root->left);
    printf("%c ", root->data);
    InOrder(root->right);
}

int main()
{
    char buf[105];

    // 多组输入，每行一棵树
    while (fgets(buf, sizeof(buf), stdin))
    {
        int i = 0;
        int p = 0;

        // 去掉 fgets 读入的换行符
        while (buf[p] != '\0')
        {
            if (buf[p] == '\n')
            {
                buf[p] = '\0';
                break;
            }
            p++;
        }

        BTNode* root = CreateTree(buf, &i);
        InOrder(root);
        printf("\n");
    }

    return 0;
}

5.4 拓展：本地工程化接口

这道题做完以后，我把这个思路整理成了本地二叉树库的标准接口，相比题目版本额外加入了数组长度参数n，避免下标越界：

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
    if (*pi >= n)
    {
        return NULL;
    }

    if (a[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }

    BTNode* newNode = BuyBTNode(a[*pi]);
    (*pi)++;

    newNode->left = BinaryTreeCreate(a, n, pi);
    newNode->right = BinaryTreeCreate(a, n, pi);

    return newNode;
}

这部分完整的本地接口整理放在了<a href="/#post/2026-08-28-binary-tree-search-destroy-build">数据结构-二叉树（五）：查找、销毁与前序序列建树</a>文章中。

六、专题总结：一条连续的递归学习路线

这一篇看起来做了五道完全不同的题，但整理之后会发现，它们并不是彼此独立的，而是一条逐步递进的学习路线。

1. 965 单值二叉树：理解「当前层条件 + 左右子树结果」的基本结构，第一次体会&&组合递归结果。
2. 100 相同的树：从单棵树递归升级为两棵树同步递归，同步比较结构与值。
3. 572 另一棵树的子树：两层递归嵌套，外层遍历寻找匹配点，内层做完整树比较；体会||的使用场景。
4. 144 前序遍历：从「判断型递归」转向「结果收集型递归」，处理动态数组、指针下标、内存管理。
5. TSINGK110 二叉树遍历：从「读取树」升级为「创建树」，用递归逆向还原树结构。

最值得记住的 5 个易错点

1. 递归返回值不能直接丢错误：isSubtree(...);正确：return isSubtree(...);或用变量接收结果再处理。
2. 明确哪个参数可以变化572 中 root 是搜索位置，可以不断变化；但 subRoot 是完整目标树，在搜索阶段不能跟着改变。
3. 先给递归函数下定义例如isSameTree(p, q)不是「再递归一下左右孩子」，而是「判断以 p 和 q 为根的两棵树是否完全相同」。一旦函数含义明确，代码通常就容易推出来。
4. 左右子树关系是 && 还是 ||由题目逻辑决定，而不是由「二叉树模板」决定。两边都要满足用 &&，一边满足即可用 ||。
5. 指针运算符优先级不能忽略returnSize++不等于(returnSize)++，宁可多加括号，也不要想当然。

写在最后

进入二叉树专题以后，越来越感觉到：二叉树题真正训练的并不是「背递归模板」，而是如何定义递归问题。

当函数定义清楚以后：

• 终止条件是什么？
• 当前结点做什么？
• 左子树返回什么？
• 右子树返回什么？
• 两个结果怎么组合？

这些问题通常都会逐渐清晰。

本篇从单棵树判断，到两棵树比较，再到寻找匹配子树、保存遍历结果、利用序列重新建树，逐步加深了二叉树递归的复杂度。其中尤其需要反复提醒自己：

递归调用不是目的，递归返回的结果如何被当前层使用，才是关键。

后续二叉树专题还会继续围绕树的递归关系和经典题型展开，把现在已经建立起来的递归思维继续练熟。