判断两棵树是否相等
时间: 2023-08-01 22:06:53 浏览: 178
判断两棵树是否相等可以通过递归的方式实现。具体步骤如下:
1. 判断两个根节点是否相等,如果不相等则返回false,否则继续下一步。
2. 递归判断左子树和右子树是否相等,如果都相等则返回true,否则返回false。
以下是Java代码实现:
```java
public boolean 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); // 递归判断左右子树是否相等
}
```
其中,TreeNode是一个树节点的类,包含了val、left、right三个属性,分别表示节点的值、左子树和右子树。
相关问题
以二叉链表作为二叉树的存储结构,判断两棵树是否相等
### 回答1:
判断两棵二叉树是否相等,可以按照以下步骤进行:
1. 判断两棵树的根节点是否相等,如果不相等,则两棵树不相等。
2. 如果两棵树的根节点相等,则递归地判断它们的左子树和右子树是否相等。
3. 如果两棵树的左子树和右子树都相等,则这两棵树相等。
在二叉链表作为二叉树的存储结构时,可以通过比较两棵树的根节点、左子树和右子树的指针来判断它们是否相等。具体实现可以参考以下代码:
```
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
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);
}
```
### 回答2:
以二叉链表作为二叉树的存储结构,判断两棵树是否相等,需要递归地比较两棵树的根节点、左子树和右子树是否相等。具体实现步骤如下:
1.判断两棵树的根节点是否相等。
2.如果两棵树的根节点相等,则继续递归比较它们的左子树和右子树是否相等。如果两棵树的左子树都为空,则它们的左子树相等;如果两棵树的左子树都不为空,则递归比较它们的左子树和右子树是否相等;如果两棵树的左子树一个为空一个不为空,则它们的左子树不相等。同样的,对于右子树也是如此。
3.如果两棵树的根节点不相等,则它们不相等。
代码实现如下:
bool isEqual(BiTreeNode *T1, BiTreeNode *T2) {
if(T1 == nullptr && T2 == nullptr) return true; //两棵树都为空,相等
if(T1 == nullptr || T2 == nullptr) return false; //两棵树只有一棵为空,不相等
if(T1->data != T2->data) return false; //两棵树的根节点不相等,不相等
return isEqual(T1->lchild, T2->lchild) && isEqual(T1->rchild, T2->rchild); //递归比较左子树和右子树是否相等
}
其中,BiTreeNode是二叉链表的节点类型,包括data(节点数据)、lchild(左子树指针)和rchild(右子树指针)。
使用以上算法,可以判断两棵树是否相等。它的时间复杂度为O(n),其中n为树中节点数。
### 回答3:
如果以二叉链表作为二叉树的存储结构,判断两棵树是否相等时需要遵循以下原则:
1. 如果两棵树都为空,则两棵树相等;
2. 如果有一棵树为空,而另一棵树不为空,则两棵树不相等;
3. 如果两棵树的根节点的数据不同,则两棵树不相等;
4. 如果两棵树的根节点的数据相同,并且它们的左子树和右子树都相等,则两棵树相等。在比较左子树和右子树是否相等时,可以使用递归的方法。
具体实现过程如下:
1. 首先判断两棵树是否为空,如果都为空,则它们相等;
2. 如果有一棵树为空,而另一棵树不为空,则它们不相等;
3. 如果两棵树的根节点的数据不同,则它们不相等;
4. 如果两棵树的根节点的数据相同,我们需要递归地比较它们的左子树和右子树是否相等,如果都相等,则它们相等,否则它们不相等。
代码实现如下:
```python
class TreeNode:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isSameTree(p: TreeNode, q: TreeNode) -> bool:
# 如果两棵树都为空,则它们相等
if not p and not q:
return True
# 如果有一棵树为空,而另一棵树不为空,则它们不相等
if not p or not q:
return False
# 如果两棵树的根节点的数据不同,则它们不相等
if p.val != q.val:
return False
# 递归比较左子树和右子树
return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
```
综上,以二叉链表作为二叉树的存储结构,判断两棵树是否相等可以通过递归比较它们的根节点、左子树和右子树的方式实现。
//判断两棵树是否镜像
判断两棵树是否镜像可以通过递归实现。具体步骤如下:
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。
相关推荐
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![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)