-
-
Notifications
You must be signed in to change notification settings - Fork 31
Expand file tree
/
Copy pathSubtree.java
More file actions
executable file
·210 lines (179 loc) · 5.47 KB
/
Copy pathSubtree.java
File metadata and controls
executable file
·210 lines (179 loc) · 5.47 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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
E
1525671122
tags: Tree, DFS
给一个binary tree s, 和一个binary tree t, 检查t是不是s的subtree.
#### DFS
- 跟 identical binary tree的写法很像
- 只有 current s.val = t.val 的时候才需要compare same tree.
- 其他情况, 继续recursively isSubtree
- 注意：即使找到T1 == T2, 但很可能只是数字相同（这里不是binary search tree!!）, 而children不同
- 所以同时要继续recursively isSubtree(T1.left, T2) ...etc.
```
/**
Given two non-empty binary trees s and t, check whether tree t has exactly
the same structure and node values with a subtree of s.
A subtree of s is a tree consists of a node in s and all of this node's descendants.
The tree s could also be considered as a subtree of itself.
Example 1:
Given tree s:
3
/ \
4 5
/ \
1 2
Given tree t:
4
/ \
1 2
Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:
3
/ \
4 5
/ \
1 2
/
0
Given tree t:
4
/ \
1 2
Return false.
*/
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null || t == null) {
return s == null && t == null;
}
return (s.val == t.val && sameTree(s, t)) || isSubtree(s.left, t) || isSubtree(s.right, t);
}
private boolean sameTree(TreeNode s, TreeNode t) {
if (s == null || t == null) {
return s == null && t == null;
}
return s.val == t.val && sameTree(s.left, t.left) && sameTree(s.right, t.right);
}
}
/*
You have two every large binary trees: T1, with millions of nodes,
and T2, with hundreds of nodes.
Create an algorithm to decide if T2 is a subtree of T1.
Example
T2 is a subtree of T1 in the following case:
1 3
/ \ /
T1 = 2 3 T2 = 4
/
4
T2 isn't a subtree of T1 in the following case:
1 3
/ \ \
T1 = 2 3 T2 = 4
/
4
Note
A tree T2 is a subtree of T1 if there exists a node n in T1
such that the subtree of n is identical to T2.
That is, if you cut off the tree at node n, the two trees would be identical.
Tags Expand
Recursion Binary Tree
*/
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
/*
Thoughts: similar to compare identical trees.
Except: only start compare if s.val == t.val, otherwise, keep dfs.
*/
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null || t == null) {
return s == null && t == null;
}
boolean checkSubTree = false;
if (s.val == t.val) {
checkSubTree = sameTree(s, t);
}
return checkSubTree || isSubtree(s.left, t) || isSubtree(s.right, t);
}
private boolean sameTree(TreeNode s, TreeNode t) {
if (s == null || t == null) {
return s == null && t == null;
}
return s.val == t.val && sameTree(s.left, t.left) && sameTree(s.right, t.right);
}
}
/**
Previous notes
Thoughts:
When T2 == null, reardless of T1 == null or NO, it can always return true;
WHen T2 != null, T1==null returns false;
1. recursively compare the two nodes: if both null, okay; if everything goes well, get deeper into the child nodes.
2. resursively check subtree: check root.left or root.right comparing with T2.
*/
public class Solution {
/**
* @param T1, T2: The roots of binary tree.
* @return: True if T2 is a subtree of T1, or false.
*/
public boolean isSubtree(TreeNode T1, TreeNode T2) {
if (T2 == null) {
return true;
} else if (T1 == null) {
return false;
} else {
return compare(T1, T2) || isSubtree(T1.left, T2) || isSubtree(T1.right, T2);
}
}
//Recursive compare
public boolean compare(TreeNode node1, TreeNode node2) {
if (node1 == null && node2 == null) {
return true;
}
if (node1 == null || node2 == null){
return false;
}
if (node1.val != node2.val) {
return false;
}
return compare(node1.left, node2.left) && compare(node1.right, node2.right);
}
}
// 2.22 recap: Find T2 first, then do a divide and conquer compare
public class Solution {
/**
* @param T1, T2: The roots of binary tree.
* @return: True if T2 is a subtree of T1, or false.
*/
public boolean isSubtree(TreeNode T1, TreeNode T2) {
if (T1 == null || T2 == null) {
return T2 == null;
}
if (T1.val == T2.val) {
return compare(T1, T2) || isSubtree(T1.left, T2) || isSubtree(T1.right, T2);
} else {
return isSubtree(T1.left, T2) || isSubtree(T1.right, T2);
}
}
public boolean compare(TreeNode T1, TreeNode T2) {
if (T1 == null && T2 == null) {
return true;
} else if (T1 == null || T2 == null) {
return false;
}
if (T1.val != T2.val) {
return false;
}
return compare(T1.left, T2.left) && compare(T1.right, T2.right);
}
}
```