1. 题目描述
给定两个二叉树,编写一个函数来检验它们是否相同。
2.问题分析
相同的树是指两个二叉树在结构上相同且节点值相等。这个问题可以很直观地通过递归来解决。我们可以先判断两个树的根节点是否相等,如果相等再递归地判断左子树和右子树是否相等。
3.算法思路
要判断两个二叉树是否相同,可以使用递归的方式。首先,我们判断两个根节点是否相等,如果相等则递归判断左子树和右子树是否相等,如果不相等则直接返回 False。如果两个根节点都为空,说明当前节点及其子树都相同,返回 True。这样就可以实现判断两个二叉树是否相同的功能。
3.1 递归函数
我们首先定义一个递归函数 isSameTree,用来判断两个树是否相同。该函数有两个参数,分别是 p 和 q,代表两个根节点。
3.2 边界情况处理
首先,我们需要处理两个边界情况。当 p 和 q 都为空时,说明当前节点及其子树都相同,返回 True。当 p 和 q 只有一个为空时,说明当前节点及其子树不相同,返回 False。
3.3 判断根节点值是否相等
如果上述边界情况都不满足,就需要判断两个根节点的值是否相等。如果不相等,说明当前节点及其子树不相同,返回 False。
3.4 递归判断左子树和右子树
如果两个根节点的值相等,就需要递归判断左子树和右子树是否相同。这可以通过调用 isSameTree 函数来完成。如果左子树和右子树都相同,说明整个树相同,返回 True。否则,返回 False。
4.代码实现
下面是利用 Python 实现的代码:
class Solution:
def isSameTree(self, 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 self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
5.测试样例
我们可以使用一些测试样例来验证代码的正确性。
测试样例1:
树 p:
```
1
\
2
/
3
```
树 q:
```
1
\
2
/
3
```
结果为 True。
测试样例2:
树 p:
```
1
\
2
```
树 q:
```
1
\
2
```
结果为 False。
测试样例3:
树 p:
```
1
\
2
```
树 q:
```
1
/
2
```
结果为 False。
6.时间复杂度分析
假设树 p 和树 q 的节点个数分别为 n1 和 n2。在最坏情况下,每个节点都需要比较一次。所以,时间复杂度为 O(n1 + n2)。
7.空间复杂度分析
在递归过程中,空间复杂度主要取决于递归调用的深度。在最坏情况下,递归调用的深度等于树的高度,即 O(max(n1, n2))。