leetcode——100.相同的树

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))。

免责声明:本文来自互联网,本站所有信息(包括但不限于文字、视频、音频、数据及图表),不保证该信息的准确性、真实性、完整性、有效性、及时性、原创性等,版权归属于原作者,如无意侵犯媒体或个人知识产权,请来电或致函告之,本站将在第一时间处理。猿码集站发布此文目的在于促进信息交流,此文观点与本站立场无关,不承担任何责任。

后端开发标签