算法判断两颗二叉树是否相似
时间: 2023-10-26 14:05:07 浏览: 165
判断两棵二叉树是否相似,需要比较它们的结构和节点值。具体方法可以使用递归实现:
1. 如果两棵树都为空,则它们相似,返回 true。
2. 如果两棵树中有一棵为空,另一棵不为空,则它们不相似,返回 false。
3. 比较两棵树的根节点的值,如果不相等,则它们不相似,返回 false。
4. 递归比较两棵树的左子树和右子树,如果都相似,则它们相似,返回 true,否则返回 false。
下面是使用 Java 实现的代码:
```java
public boolean isSimilar(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) {
return true;
}
if (root1 == null || root2 == null) {
return false;
}
if (root1.val != root2.val) {
return false;
}
boolean left = isSimilar(root1.left, root2.left);
boolean right = isSimilar(root1.right, root2.right);
return left && right;
}
```
其中,TreeNode 表示二叉树节点的数据结构,包含 val、left、right 三个属性。
相关问题
利用python设计判断两颗二叉树是否相同的算法
可以使用递归的方式判断两颗二叉树是否相同。具体实现可以参考以下代码:
```python
# 定义二叉树节点类
class TreeNode:
def __init__(self, val=0, 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)
```
在上述代码中,我们首先判断两个二叉树是否均为空,如果是,则认为它们相同;如果一个二叉树为空,另一个不为空,则认为它们不相同;如果两个二叉树的根节点的值不相同,则认为它们不相同;最后,我们递归判断两个二叉树的左子树和右子树是否相同。
设计C++算法判断两个二叉树是否相同
以下是C++中判断两个二叉树是否相同的算法:
1. 递归算法
```C++
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == nullptr && q == nullptr) {
return true;
}
if (p == nullptr || q == nullptr) {
return false;
}
if (p->val != q->val) {
return false;
}
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
```
2. 非递归算法
```C++
bool isSameTree(TreeNode* p, TreeNode* q) {
stack<TreeNode*> s;
s.push(p);
s.push(q);
while (!s.empty()) {
p = s.top();
s.pop();
q = s.top();
s.pop();
if (p == nullptr && q == nullptr) {
continue;
}
if (p == nullptr || q == nullptr) {
return false;
}
if (p->val != q->val) {
return false;
}
s.push(p->left);
s.push(q->left);
s.push(p->right);
s.push(q->right);
}
return true;
}
```