【数据结构与算法】判断一棵树是否是另一棵树的子树
【摘要】 给你两棵二叉树root和subRoot。检验root中是否包含和subRoot具有相同结构和节点值的子树。如果存在，返回true；否则，返回false。二叉树tree的一棵子树包括tree的某个节点和这个节点的所有后代节点。tree也可以看做它自身的一棵子树。
目录
一、问题描述
给你两棵二叉树
root和subRoot。检验root中是否包含和subRoot具有相同结构和节点值的子树。如果存在，返回true；否则，返回false。二叉树
tree的一棵子树包括tree的某个节点和这个节点的所有后代节点。tree也可以看做它自身的一棵子树。
二、解题思路
解题思路:
第一步：
如果第二棵树是空树，可以判定为true（空树是任何树的子树）
如果第二棵树不为空，第一棵树为空，则判定为false
这两步判断，同时也可以避免后面对空指针解引用
第二步：
从第一棵树的根结点开始，判断第二棵树与他的当前节点的值是否相同，如果相同——借用之前已经实现好的函数（判断两棵树是否相同），判断第二棵树是否与第一棵树当前节点之后的结构和数据相同
第三步：
如果未判定相同，分别递归调用第一棵树的左子树和右子树，两条路如果有一路返回了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);
}
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）