cpp 判断二叉树b是不是a的子结构
时间: 2023-12-16 22:02:29 浏览: 32
可以使用递归的方法判断二叉树b是否是二叉树a的子结构,具体思路如下:
1. 首先在二叉树a中找到与二叉树b根节点相同的节点,可以使用深度优先搜索。
2. 找到相同的节点后,分别判断以该节点为根节点的子树是否包含二叉树b。可以再次使用递归的方法判断。
3. 如果以该节点为根节点的子树包含二叉树b,则返回true,否则继续在二叉树a中搜索与二叉树b根节点相同的节点。
下面是一个示例代码实现:
```cpp
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
bool isSubStructure(TreeNode* A, TreeNode* B) {
if (A == NULL || B == NULL) {
return false;
}
return isSubTree(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
}
bool isSubTree(TreeNode* A, TreeNode* B) {
if (B == NULL) {
return true;
}
if (A == NULL || A->val != B->val) {
return false;
}
return isSubTree(A->left, B->left) && isSubTree(A->right, B->right);
}
```
其中,isSubStructure函数用于判断二叉树B是否是二叉树A的子结构,isSubTree函数用于判断以节点A为根节点的子树是否包含二叉树B。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)