05 August 2008
DFS 暴力匹配 O(∣s∣×∣t∣)
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
/**
* 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 isSubtree(TreeNode root, TreeNode subRoot) {
if (subRoot == null) {
return true;
}
if (root == null) { // subRoot is not null here
return false;
}
// 当前结点是比较是否为Same Tree，左右子树是比较是否是Sub Tree
return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
private boolean isSameTree(TreeNode s, TreeNode t) {
if (s == null && t == null) {
return true;
}
if (s == null || t == null) {
return false;
}
if (s.val != t.val) {
return false;
}
return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) return false;
if (isSame(s, t)) return true;
return isSubtree(s.left, t) || isSubtree(s.right, t);
}
private boolean isSame(TreeNode s, TreeNode t) {
if (s == null && t == null) return true;
if (s == null || t == null) return false;
if (s.val != t.val) return false;
return isSame(s.left, t.left) && isSame(s.right, t.right);
}
}
树哈希 O(argπ(max{∣s∣,∣t∣}))
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
class Solution {
static final int MAX_N = 1005;
static final int MOD = 1000000007;
boolean[] vis = new boolean[MAX_N];
int[] p = new int[MAX_N];
int tot;
Map<TreeNode, int[]> hS = new HashMap<TreeNode, int[]>();
Map<TreeNode, int[]> hT = new HashMap<TreeNode, int[]>();
public boolean isSubtree(TreeNode s, TreeNode t) {
getPrime();
dfs(s, hS);
dfs(t, hT);
int tHash = hT.get(t)[0];
for (Map.Entry<TreeNode, int[]> entry : hS.entrySet()) {
if (entry.getValue()[0] == tHash) {
return true;
}
}
return false;
}
public void getPrime() {
vis[0] = vis[1] = true;
tot = 0;
for (int i = 2; i < MAX_N; ++i) {
if (!vis[i]) {
p[++tot] = i;
}
for (int j = 1; j <= tot && i * p[j] < MAX_N; ++j) {
vis[i * p[j]] = true;
if (i % p[j] == 0) {
break;
}
}
}
}
public void dfs(TreeNode o, Map<TreeNode, int[]> h) {
h.put(o, new int[]{o.val, 1});
if (o.left == null && o.right == null) {
return;
}
if (o.left != null) {
dfs(o.left, h);
int[] val = h.get(o);
val[1] += h.get(o.left)[1];
val[0] = (int) ((val[0] + (31L * h.get(o.left)[0] * p[h.get(o.left)[1]]) % MOD) % MOD);
}
if (o.right != null) {
dfs(o.right, h);
int[] val = h.get(o);
val[1] += h.get(o.right)[1];
val[0] = (int) ((val[0] + (179L * h.get(o.right)[0] * p[h.get(o.right)[1]]) % MOD) % MOD);
}
}
}