【数据结构与算法经典例题】判断一棵树是否是另一棵树的子树

用户11396077

发布于 2024-12-06 19:26:21

790

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

一、问题描述

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。 原题出自 572. 另一棵树的子树 - 力扣（LeetCode）

二、解题思路

解题思路: 第一步： 如果第二棵树是空树，可以判定为true（空树是任何树的子树） 如果第二棵树不为空，第一棵树为空，则判定为false 这两步判断，同时也可以避免后面对空指针解引用 第二步： 从第一棵树的根结点开始，判断第二棵树与他的当前节点的值是否相同，如果相同——借用之前已经实现好的函数（判断两棵树是否相同），判断第二棵树是否与第一棵树当前节点之后的结构和数据相同 关于子函数更多细节请参考文章 【数据结构与算法经典例题】判断两棵二叉树是否相同-CSDN博客 第三步： 如果未判定相同，分别递归调用第一棵树的左子树和右子树，两条路如果有一路返回了true，就说明第一棵树中出现了与第二棵树相同的结构和数据

三、C语言实现代码

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    
};

typedef struct TreeNode TNode;
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 && subRoot == NULL)
        return true;
    if (root == NULL || subRoot == NULL)
        return false;
    if (root->val == subRoot->val)//如果两个结点值相同，判断两棵树是否相同
        if (isSameTree(root, subRoot))
            return true;
    //否则，继续向下查找
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}