判断一个二叉树A是否是另一个二叉树B的子节点
时间: 2023-09-06 12:12:19 浏览: 48
要判断一个二叉树A是否是另一个二叉树B的子节点,可以采用递归的方式,分别判断A和B的根节点是否相同,如果相同再分别判断A的左右子树是否是B的左右子树的子节点。
具体实现可以按照如下代码:
```
bool isSubTree(TreeNode* A, TreeNode* B) {
if (A == nullptr || B == nullptr) {
return false;
}
if (A->val == B->val && isSameTree(A, B)) {
return true;
}
return isSubTree(A->left, B) || isSubTree(A->right, B);
}
bool isSameTree(TreeNode* A, TreeNode* B) {
if (A == nullptr && B == nullptr) {
return true;
}
if (A == nullptr || B == nullptr) {
return false;
}
if (A->val != B->val) {
return false;
}
return isSameTree(A->left, B->left) && isSameTree(A->right, B->right);
}
```
其中 `isSubTree` 函数判断A是否是B的子节点, `isSameTree` 函数判断两棵树是否相同。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)