【LeetCode&数据结构】二叉树的应用（一）——单值二叉树问题、相同的树问题、对称二叉树问题、另一棵树的子树问题详解

艾莉丝努力练剑

发布于 2025-11-12 18:57:46

1250

文章被收录于专栏：C / C++C / C++

前言：牛客网和LeetCode的刷题都不可或缺，我们都要做一做，无论是参加竞赛还是笔试面试，至少能提升你的代码能力！洛谷的题目也可以去做一做。力扣的题目对提升代码能力很有帮助，需要有一点基础，几乎都是接口型的题目，关于接口型和IO型的区别我们在本专栏的第一篇【LeetCode】力扣题——轮转数组、消失的数字、数组串联中就介绍过了，这里不再赘述，我们进入今天的力扣题目介绍——

正文

一、单值二叉树问题

965. 单值二叉树

博主题解链接：若根节点root非空，让root跟左右孩子节点的值进行比较

题目描述：

题目示例和提示——

（一）思路

我们的思路是：根左右，若根节点root非空，让root跟左右孩子节点的值进行比较。

（二）解题过程

（三）完整代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isUnivalTree(struct TreeNode* root) {
    if(root == NULL)
    {
        return true;
    }
    //根节点root非空，root跟左右孩子节点的值进行比较
    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);
}

复杂度：时间复杂度：O(logn)，空间复杂度：O(n)。

二、相同的树问题

100. 相同的树

博主题解链接：分都为空、其中一个为空、都不为空三种情况讨论，解决相同的树问题

题目描述：

题目示例和提示——

（一）思路

我们的思路是：可以分都为空、其中一个为空、都不为空三种情况讨论。

（二）解题过程

（三）完整代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
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);
}

复杂度：时间复杂度：O(logn)，空间复杂度：O(n)。

三、对称二叉树问题

101. 对称二叉树

博主题解链接：利用相同的树用过的方法：分三种情况讨论，结合对称性解决问题

题目描述：

（一）思路

我们的思路是：利用相同的树用过的方法：分三种情况讨论，并且结合对称性。

（二）解题过程

示例1：

示例2：

我们要把这道题和前面的【相同的树】联系起来：

【相同的树】：

代码实现：

【相同的树】的代码我们可以拿过来改一改，直接就可以用：
我们调用相同的树的代码，我们需要稍微地改一下，原本我们比较的是p的左和q的左是否相同、p的右和q的右是否相同，在这里我们是比较是否是对称的二叉树，所以改成p的左(left)和q的右(right)比较是否相同、p的右和q的左比较是否相同，并且把最后的结果给返回——

代码实现完了，我们跟着流程再走一遍看一下——

（三）完整代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
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->right) && isSameTree(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root) 
{
    return isSameTree(root->left,root->right);
}

复杂度：时间复杂度：O(logn)，空间复杂度：O(n)。

四、另一棵树的子树问题

572. 另一棵树的子树

博主题解链接：分三种情况讨论解决另一棵树的子树

题目描述：

题目示例和提示——

（一）思路

我们的思路是：分为空、其中一个为空、都不为空三种情况讨论。

（二）解题过程

（三）完整代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
typedef struct TreeNode TreeNode;
bool isSameTree(TreeNode* p,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;
    }
    if(isSameTree(root,subRoot))
    {
        return true;
    }
    return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

复杂度：时间复杂度：O(logn)，空间复杂度：O(n)。

结尾

往期回顾：

【LeetCode&数据结构】栈和队列的应用——设计循环队列问题详解

由于本专栏的篇数越来越多，为了避免文章链接挂太多影响观感，博主之后的每一篇力扣刷题详解都只会附上前一篇的链接，最后一次完整链接是在之后会发布的【栈的应用——有效的括号问题详解】和【单链表的应用——环形链表问题详解】的文章结尾，本意是为了方便大家找到相应的详细的题解，现在文章多了，铸币博主没办法一一罗列，而且还会有“凑字数”的嫌疑，力扣刷题专栏的链接每次都会放在文章开头的位置，大家可自行前往！感谢大家的理解与支持！

【LeetCode&数据结构】栈的应用——有效的括号问题详解

【LeetCode&数据结构】单链表的应用——环形链表问题详解