forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path100. Same Tree.java
More file actions
executable file
·100 lines (79 loc) · 2.19 KB
/
Copy path100. Same Tree.java
File metadata and controls
executable file
·100 lines (79 loc) · 2.19 KB
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
E
tags: Tree, DFS, BFS
time: O(n)
space: O(logn)
给两个 binary tree, 看两个tree是否identical.
#### Method1: DFS
- DFS. 确定leaf条件, && with all dfs(sub1, sub2).
- 这里无论如何都要走过所有的node, 所以dfs更加合适, 好写.
#### Method2: BFS with 2 queues
- 两个queue存每个tree的所有current level node. Check equality, check queue size.
- Populate next level by nodes at current level.
```
/*
Given two binary trees, 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.
Example 1:
Input: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
Output: true
Example 2:
Input: 1 1
/ \
2 2
[1,2], [1,null,2]
Output: false
Example 3:
Input: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
Output: false
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
/*
Method1: DFS
Use the function itself with dfs.
Check p == q, p.left==q.left, p.right==q.right
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null || q == null) return p == null && q == null;
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
// Method2: BFS
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
Queue<TreeNode> pp = new LinkedList<>();
Queue<TreeNode> qq = new LinkedList<>();
pp.offer(p);
qq.offer(q);
while (!pp.isEmpty() && !qq.isEmpty()) {
p = pp.poll();
q = qq.poll();
if (p == null && q == null) continue;
if (p == null ^ q == null) return false;
if (p.val != q.val) return false;
offer(p, pp);
offer(q, qq);
}
return true;
}
private void offer(TreeNode node, Queue<TreeNode> queue) {
queue.offer(node.left);
queue.offer(node.right);
}
}
```