怎样判断一个二叉树是否为另一棵树的子树
时间: 2023-09-16 08:10:06 浏览: 110
判断一个二叉树是否为另一棵树的子树,可以采用递归的方法,先判断当前根节点是否相同,若相同则递归判断左右子树是否相同,若不同则递归判断原二叉树的左右子树是否为目标树的子树。
具体实现步骤如下:
1. 判断当前节点是否为空,若为空则返回 false。
2. 判断当前节点是否与目标树的根节点相同,若相同则递归判断左右子树是否相同。
3. 若当前节点与目标树的根节点不同,则递归判断原二叉树的左右子树是否为目标树的子树。
具体实现代码如下(假设 TreeNode 为二叉树节点的数据结构):
```
bool isSubtree(TreeNode* s, TreeNode* t) {
if (!s) return false; // 若当前节点为空,返回 false
if (isSameTree(s, t)) return true; // 若当前节点与目标树根节点相同,递归判断左右子树是否相同
return isSubtree(s->left, t) || isSubtree(s->right, t); // 若不同,则递归判断原二叉树的左右子树是否为目标树的子树
}
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) return true; // 若两个节点均为空,返回 true
if (!p || !q) return false; // 若其中一个节点为空,返回 false
if (p->val != q->val) return false; // 若两个节点的值不同,返回 false
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); // 递归判断左右子树是否相同
}
```
其中 isSameTree 函数用于判断两个节点以及它们的子树是否相同。