给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:
1
2
3
4
5
6
7
| 输入: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
输出: true
|
示例 2:
1
2
3
4
5
6
7
| 输入: 1 1
/ \
2 2
[1,2], [1,null,2]
输出: false
|
示例 3:
1
2
3
4
5
6
7
| 输入: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
输出: false
|
方法一：DFS
对于两棵树 root1，root2，如果 root1 和 root2 都为空，则返回 true；如果 root1 和 root2 中有一个为空，另一个不为空，则返回false。如果都不为空且它们的值相等，则递归判断左右子树。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null){
return true;
}
if(p == null || q == null){
return false;
}
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
|
时间复杂度O(min(m, n))，m，n为两棵树的节点数。空间复杂度O(min(m, n))。
方法二：BFS
我们使用两个队列来存储二叉树的层次遍历。判断这个队列中的结点值是否相同即可。
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
27
28
29
30
31
32
33
| class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null){
return true;
}
if(p == null || q == null){
return false;
}
Queue<TreeNode> q1 = new LinkedList<>();
Queue<TreeNode> q2 = new LinkedList<>();
q1.offer(p);
q2.offer(q);
while(!q1.isEmpty() && !q2.isEmpty()){
TreeNode n1 = q1.poll(), n2 = q2.poll();
if(n1.val != n2.val){
return false;
}
if( (n1.left == null ^ n2.left == null) || (n1.right == null ^ n2.right == null) ){
return false;
}
if(n1.left != null) q1.offer(n1.left);
if(n1.right != null) q1.offer(n1.right);
if(n2.left != null) q2.offer(n2.left);
if(n2.right != null) q2.offer(n2.right);
}
return true;
}
}
|
时间复杂度O(min(m, n))，m，n为两棵树的节点数。空间复杂度O(min(m, n))。