题目描述
给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:
1
2
3
4
5
6
7
8
9
| 输入:
1 1
/ \ / \
2 3 2 3
[1, 2, 3], [1, 2, 3]
输出: true
|
示例 2:
1
2
3
4
5
6
7
8
9
| 输入:
1 1
/ \
2 2
[1, 2], [1, null, 2]
输出: false
|
示例 3:
1
2
3
4
5
6
7
8
9
| 输入:
1 1
/ \ / \
2 1 1 2
[1, 2, 1], [1, 1, 2]
输出: false
|
题解
此题是另外一道题的一个子解题步骤：另一个树的子树，根据题目描述，我们可以使用深度优先搜索，首先判断如果两个二叉树都为空，则两个二叉树相同。如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同【这也是递归的终止条件】。然后判断两个树的根节点值是否相同，接下来递归的方式处理两个树的左子树和右子树，如果都相同，则为相同的树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null || q == null) {
return p == null && q == null;
} else {
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
|
复杂度分析
- 时间复杂度：O(min(m, n))，其中 m 和 n 分别是两个二叉树的节点数。对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会访问到该节点，因此被访问到的节点数不会超过较小的二叉树的节点数。
- 空间复杂度：O(min(m, n))，其中 m 和 n 分别是两个二叉树的节点数。空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。
来源
相同的树 | 力扣（LeetCode）
相同的树 | 题解（LeetCode）
