C语言中怎样判断一个二叉树是否为另一棵树的子树
时间: 2024-03-10 21:46:56 浏览: 114
C言中判断一个二叉树是否为另一棵树的子树,也可以采用递归的方法,具体实现方式与前面提到的类似。
具体实现步骤如下:
1. 判断当前节点是否为空,若为空则返回 false。
2. 判断当前节点是否与目标树的根节点相同,若相同则递归判断左右子树是否相同。
3. 若当前节点与目标树的根节点不同,则递归判断原二叉树的左右子树是否为目标树的子树。
具体实现代码如下(假设 TreeNode 为二叉树节点的数据结构):
```
bool isSubtree(struct TreeNode* s, struct TreeNode* t){
if (!s) return false; // 若当前节点为空,返回 false
if (isSameTree(s, t)) return true; // 若当前节点与目标树根节点相同,递归判断左右子树是否相同
return isSubtree(s->left, t) || isSubtree(s->right, t); // 若不同,则递归判断原二叉树的左右子树是否为目标树的子树
}
bool isSameTree(struct TreeNode* p, struct 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 函数用于判断两个节点以及它们的子树是否相同。
阅读全文
相关推荐


















