-
Notifications
You must be signed in to change notification settings - Fork 1
/
LeafSimilarTrees.java
42 lines (39 loc) · 1.04 KB
/
LeafSimilarTrees.java
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
import java.util.ArrayList;
import java.util.List;
/**
* 872. Leaf-Similar Trees
* DFS
* @author LBW
*/
public class LeafSimilarTrees {
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
List<Integer> leaf1 = getleaf(root1);
List<Integer> leaf2 = getleaf(root2);
if (leaf1.size() != leaf2.size())
return false;
int n = leaf1.size();
for (int i = 0; i < n; i++) {
if (!leaf1.get(i).equals(leaf2.get(i))) {
return false;
}
}
return true;
}
private List<Integer> getleaf(TreeNode root) {
List<Integer> list = new ArrayList<>();
dfs(root, list);
return list;
}
private void dfs(TreeNode node, List<Integer> list) {
if (node.left == null && node.right == null) {
list.add(node.val);
return;
}
if (node.left != null) {
dfs(node.left, list);
}
if (node.right != null) {
dfs(node.right, list);
}
}
}