Leetcode/src/main/java/com/fishercoder/solutions/fourththousand/_3249.java at master · fishercoder1534/Leetcode · GitHub

Name: Leetcode/src/main/java/com/fishercoder/solutions/fourththousand/_3249.java at master · fishercoder1534/Leetcode · GitHub
Rating: 4.8 (6391 reviews)
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
packagecom.fishercoder.solutions.fourththousand;

importjava.util.ArrayList;
importjava.util.HashMap;
importjava.util.List;
importjava.util.Map;

publicclass_3249 {
publicstaticclassSolution1 {
/*
 * My completely original solution during the contest.
 */
classTreeNode {
intval;
List<TreeNode> children;
inttotalChildrenCount;

publicTreeNode(intval) {
this.val = val;
this.children = newArrayList<>();
this.totalChildrenCount = 1; // count itself as its own child
 }
 }

intgoodNodes = 0;

publicintcountGoodNodes(int[][] edges) {
if (edges == null || edges.length == 0 || edges[0].length == 0) {
return0;
 }
TreeNoderoot = buildTree(edges);
postOrder(root);
dfs(root);
returngoodNodes;
 }

privatevoiddfs(TreeNoderoot) {
if (root == null || root.children.isEmpty()) {
return;
 }
intsize = root.children.get(0).totalChildrenCount;
if (size == 0) {
return;
 }
booleanpossiblyGoodNode = true;
for (TreeNodechild : root.children) {
if (child.totalChildrenCount != size) {
possiblyGoodNode = false;
break;
 }
 }
if (possiblyGoodNode) {
goodNodes++;
 }
for (TreeNodechild : root.children) {
dfs(child);
 }
 }

privateintpostOrder(TreeNoderoot) {
if (root == null) {
return0;
 }
if (root.children.isEmpty()) {
goodNodes++;
return1;
 }
inttotalChildrenCount = 1;
for (TreeNodechild : root.children) {
intcount = postOrder(child);
totalChildrenCount += count;
 }
root.totalChildrenCount = totalChildrenCount;
returntotalChildrenCount;
 }

privateTreeNodebuildTree(int[][] edges) {
Map<Integer, TreeNode> map = newHashMap<>();
for (inti = 0; i < edges.length; i++) {
if (edges[i][0] == 0 || edges[i][1] == 0) {
if (edges[i][0] == 0) {
TreeNodeparent = map.getOrDefault(edges[i][0], newTreeNode(edges[i][0]));
TreeNodechild = map.getOrDefault(edges[i][1], newTreeNode(edges[i][1]));
parent.children.add(child);
map.put(edges[i][0], parent);
map.put(edges[i][1], child);
 } else {
TreeNodeparent = map.getOrDefault(edges[i][1], newTreeNode(edges[i][1]));
TreeNodechild = map.getOrDefault(edges[i][0], newTreeNode(edges[i][0]));
parent.children.add(child);
map.put(edges[i][1], parent);
map.put(edges[i][0], child);
 }
 } else {
if (map.containsKey(edges[i][0])) {
TreeNodeparent = map.get(edges[i][0]);
TreeNodechild = map.getOrDefault(edges[i][1], newTreeNode(edges[i][1]));
parent.children.add(child);
map.put(edges[i][0], parent);
map.put(edges[i][1], child);
 } elseif (map.containsKey(edges[i][1])) {
TreeNodeparent = map.get(edges[i][1]);
TreeNodechild = map.getOrDefault(edges[i][0], newTreeNode(edges[i][0]));
parent.children.add(child);
map.put(edges[i][1], parent);
map.put(edges[i][0], child);
 }
 }
 }
returnmap.get(0);
 }
 }
}