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
| class Solution {
private int ans;
public int longestPath(int[] parent, String s) {
ans = 1;
Map<Integer, List<Integer>> nodeNeighbors = new HashMap<>();
for (int i = 1; i < parent.length; i++) {
int currNode = i, currNodeParent = parent[i];
nodeNeighbors.computeIfAbsent(currNodeParent, (key) -> new ArrayList<>()).add(currNode);
}
dfs(0, nodeNeighbors, s.toCharArray());
return ans;
}
private int dfs(int currNode, Map<Integer, List<Integer>> nodeNeighbors, char[] nodeChar) {
int currNodeMaxPath = 1;
if (nodeNeighbors.containsKey(currNode)) {
int maxOne = 0, maxTwo = 0;
for (int neighbor : nodeNeighbors.get(currNode)) {
char neighborChar = nodeChar[neighbor];
int subtreeMaxPath = dfs(neighbor, nodeNeighbors, nodeChar);
if (neighborChar != nodeChar[currNode]) {
if (subtreeMaxPath > maxTwo) {
maxOne = maxTwo;
maxTwo = subtreeMaxPath;
} else if (subtreeMaxPath > maxOne) {
maxOne = subtreeMaxPath;
}
}
}
ans = Math.max(ans, maxOne + maxTwo + 1);
currNodeMaxPath = maxTwo + 1;
}
return currNodeMaxPath;
}
}
|
递归函数获得从给定node开始往下延伸最远的距离. 因此在某个node的时候, 我们获得该node所有children的最长距离. 取chilren的char和自己char不同的中延伸最远的两个, 让他们相加再加上1(即当前node自己), 然后和global variable比较. 最终返回的时候, 返回和自己char不同的children中最长的path长度 + 1(即自己).
时间复杂度: O(n)
空间复杂度: O(n)
