![https://leetcode.com/problems/same-tree/]
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
1
2
3
4
| Example 1:
Input: p = [1,2,3], q = [1,2,3]
Output: true
|
1
2
3
4
| Example 2:
Input: p = [1,2], q = [1,null,2]
Output: false
|
1
2
3
4
| Example 3:
Input: p = [1,2,1], q = [1,1,2]
Output: false
|
Constraints:
- The number of nodes in both trees is in the range [0, 100].
- -104 <= Node.val <= 104
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| /**
* Definition for a binary tree node.
* 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;
* }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
List<TreeNode> queue1 = new ArrayList<>();
List<TreeNode> queue2 = new ArrayList<>();
queue1.add(p);
queue2.add(q);
while (!queue1.isEmpty() || !queue2.isEmpty()) {
if (queue1.isEmpty()) {
return false;
}
if (queue2.isEmpty()) {
return false;
}
TreeNode a = queue1.remove(0);
TreeNode b = queue2.remove(0);
if (a == null && a == b) {
continue;
}
if (a == null || b == null) {
return false;
}
if (a.val != b.val) {
return false;
}
queue1.add(a.left);
queue2.add(b.left);
queue1.add(a.right);
queue2.add(b.right);
}
return true;
}
public boolean isSameTree2(TreeNode p, TreeNode q) {
if (p == null && p == q) {
return true;
}
if (p == null || q == null) {
return false;
}
if (p.val != q.val) {
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
|