給出一棵樹(shù)，parent[i]代表節(jié)點(diǎn)i的父節(jié)點(diǎn)ID，以及一個(gè)字符串s，s[i]代表每個(gè)節(jié)點(diǎn)的字符值，求樹(shù)中最長(zhǎng)的一條滿(mǎn)足相鄰節(jié)點(diǎn)字符值不同的path的長(zhǎng)度，DFS
先用dict建樹(shù)，保存與每個(gè)節(jié)點(diǎn)i相連的節(jié)點(diǎn)，然后DFS到每個(gè)節(jié)點(diǎn)處時(shí)，若為葉子結(jié)點(diǎn)，返回1，否則搜索該節(jié)點(diǎn)所有子節(jié)點(diǎn)，找出每個(gè)子樹(shù)i中符合要求的path長(zhǎng)度l[i]，如果子節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)字符值不一樣，那么以當(dāng)前節(jié)點(diǎn)為根，經(jīng)過(guò)子樹(shù)i最多可以取長(zhǎng)度為max(l[1:i-1]) + l[i] + 1，DFS每一層返回值為max(l)
1 #2246
2 #Runtime: 1720 ms (Beats 70.91%)
3 #Memory: 139.6 MB (Beats 72.12%)
4
5 class Solution(object):
6 def longestPath(self, parent, s):
7 """
8 :type parent: List[int]
9 :type s: str
10 :rtype: int
11 """
12 p = defaultdict(list)
13 for i in range(1, len(parent)):
14 p[parent[i]].append(i)
15 self.ans = 1
16
17 def DFS(r):
18 if not p[r]:
19 return 1
20 t = 1
21 for i in p[r]:
22 l = DFS(i)
23 if s[r] != s[i]:
24 self.ans = max(l + t, self.ans)
25 t = max(t, l + 1)
26 return t
27
28 DFS(0)
29 return self.ans