使用c++语言,根据给出的二叉树a、b的层次序列,判断b是否是a的一个子树
时间: 2024-02-25 18:59:35 浏览: 21
以下是使用C++语言判断b是否是a的子树的代码:
```c++
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
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(TreeNode* s, TreeNode* t) {
if (s == NULL) {
return false;
}
if (isSameTree(s, t)) {
return true;
}
return isSubtree(s->left, t) || isSubtree(s->right, t);
}
int main() {
// 构造二叉树a
TreeNode* a = new TreeNode(3);
a->left = new TreeNode(4);
a->right = new TreeNode(5);
a->left->left = new TreeNode(1);
a->left->right = new TreeNode(2);
// 构造二叉树b
TreeNode* b = new TreeNode(4);
b->left = new TreeNode(1);
b->right = new TreeNode(2);
// 判断b是否是a的子树
if (isSubtree(a, b)) {
cout << "b is a subtree of a" << endl;
} else {
cout << "b is not a subtree of a" << endl;
}
return 0;
}
```
首先定义一个结构体`TreeNode`表示二叉树节点,包括节点的值`val`和左右子树指针`left`和`right`。
然后定义一个函数`isSameTree`判断两个二叉树是否相同。如果两个二叉树都为空,则它们相同;如果其中一个为空,则它们不相同;如果两个二叉树的根节点值不相同,则它们不相同;否则递归地判断左右子树是否相同。
接着定义一个函数`isSubtree`判断二叉树`t`是否是二叉树`s`的子树。如果`s`为空,则`t`不可能是其子树;如果`s`和`t`相同,则`t`是`s`的子树;否则递归地判断`s`的左右子树是否包含`t`。
最后在`main`函数中构造二叉树`a`和`b`,并调用`isSubtree`函数判断`b`是否是`a`的子树。