采用二叉链表存储结构,判别两棵二叉树是否相等,给出代码
时间: 2024-10-20 15:15:27 浏览: 9
头歌数据结构二叉树的二叉链表存储及基本操作
5星 · 资源好评率100%
在使用二叉链表存储结构判断两棵树是否相等时,我们需要比较两棵树的节点值、左子树以及右子树是否都完全一致。以下是使用递归的方式实现 Java 代码:
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true; // 如果两个都是空节点,则它们相等
} else if (p == null || q == null) {
return false; // 如果其中一个为空,另一个不为空,则不相等
} else {
// 比较当前节点值是否相等,然后递归检查左右子树是否也相等
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
}
```
在这个 `isSameTree` 函数中,我们首先检查两个节点是否同时为 `null`,如果都是则返回 `true`;然后检查其中一个是否 `null` 而另一个不是,此时返回 `false`。最后,若节点值相等并且其左右子树经过递归调用也都相等,那么这两棵树就被认为是相同的。
阅读全文