//判断两棵树是否镜像
时间: 2023-07-08 22:24:37 浏览: 52
判断两棵树是否镜像可以通过递归实现。具体步骤如下:
1. 如果两棵树都为空,返回 true。
2. 如果其中一棵树为空,返回 false。
3. 如果两棵树的根节点的值不相等,返回 false。
4. 判断第一棵树的左子树和第二棵树的右子树是否镜像,同时判断第一棵树的右子树和第二棵树的左子树是否镜像,如果都满足返回 true,否则返回 false。
代码实现如下:
```c++
bool isMirror(TreeNode* t1, TreeNode* t2) {
if (t1 == nullptr && t2 == nullptr) {
return true;
}
if (t1 == nullptr || t2 == nullptr) {
return false;
}
if (t1->val != t2->val) {
return false;
}
return isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);
}
```
其中,TreeNode 是二叉树的节点结构体,包含指向左右子树的指针和节点值的成员变量 val。
相关问题
判断一棵树是否镜像
判断一棵树是否镜像也可以通过递归实现。具体步骤如下:
1. 如果树为空,返回 true。
2. 判断树的左子树和右子树是否镜像,如果都满足返回 true,否则返回 false。
代码实现如下:
```c++
bool isSymmetric(TreeNode* root) {
if (root == nullptr) {
return true;
}
return isMirror(root->left, root->right);
}
```
其中,isMirror 函数是判断两棵树是否镜像的函数,和上一个问题的代码实现相同。
判断二叉树是否镜像
判断一棵二叉树是否是镜像二叉树的方法是:判断其左右子树是否镜像对称。具体实现可以使用递归算法,从根节点开始,判断左右子树是否镜像对称,如果是,则递归判断左子树的左子树和右子树的右子树是否镜像对称,以及左子树的右子树和右子树的左子树是否镜像对称。如果所有的节点都满足镜像对称的条件,则该二叉树是镜像二叉树,否则不是。
以下是一个示例代码:
```
bool isMirror(TreeNode* left, TreeNode* right) {
if (left == nullptr && right == nullptr) return true;
if (left == nullptr || right == nullptr) return false;
if (left->val != right->val) return false;
return isMirror(left->left, right->right) && isMirror(left->right, right->left);
}
bool isSymmetric(TreeNode* root) {
if (root == nullptr) return true;
return isMirror(root->left, root->right);
}
```
该算法的时间复杂度为O(n),其中n是二叉树中节点的数量。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)