-
Notifications
You must be signed in to change notification settings - Fork 112
/
Solution.java
75 lines (57 loc) · 1.9 KB
/
Solution.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
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
import java.util.ArrayList;
import java.util.List;
/**
* @author Oleg Cherednik
* @since 31.03.2019
*/
public class Solution {
public static void main(String... args) {
System.out.println(getLongestPathLength(createTree())); // 18
}
private static Node createTree() {
Node e = new Node("e", 2);
e.children.add(new Node("g", 1));
e.children.add(new Node("h", 3));
Node d = new Node("d", 8);
d.children.add(e);
d.children.add(new Node("f", 4));
Node a = new Node("a", 0);
a.children.add(new Node("b", 3));
a.children.add(new Node("c", 5));
a.children.add(d);
return a;
}
public static int getLongestPathLength(Node root) {
Data data = new Data(0);
dfs(root, data);
return data.length;
}
private static int dfs(Node node, Data maxLengthPath) {
if (node == null || node.children.isEmpty())
return 0;
List<Data> children = new ArrayList<>();
for (Node child : node.children)
children.add(new Data(child.weight + dfs(child, maxLengthPath)));
children.sort((one, two) -> Integer.compare(two.length, one.length));
maxLengthPath.set(children.size() > 1 ? children.get(0).length + children.get(1).length : children.get(0).length);
return children.get(0).length;
}
private static final class Node {
private final String id;
private final int weight;
private final List<Node> children = new ArrayList<>();
public Node(String id, int weight) {
this.id = id;
this.weight = weight;
}
}
private static final class Data {
private int length;
public Data(int length) {
this.length = length;
}
public void set(int length) {
this.length = Math.max(this.length, length);
}
}
}