在Python中找出树中特殊节点的程序
假设我们有一个称为“tree”的二维值列表，它表示一元树，另一个名为“color”的值列表。该树表示为邻接表，其根为tree[0]。
第i个节点的特征-
tree[i]是它的子代和父代。
color[i]是它的颜色。
如果子树中根为N的每个节点都有唯一的颜色，则我们称节点N为“特殊”节点。因此，我们有了这棵树，我们必须找出特殊节点的数量。
So, if the input is like tree = [ [1,2], [0], [0,3], [2] ]
colors=[1,2,1,1]，则输出为2。
在线示例
让我们看下面的实现以更好地理解-
import collections
class Solution:
def solve(self, tree, color):
self.result = 0
def dfs(node, prev):
colors = {color[node]}
for child in tree[node]:
if child != prev:
child_colors = dfs(child, node)
if colors and child_colors:
if self.check_intersection(colors, child_colors):
colors = None
else:
if len(colors) < len(child_colors):
child_colors |= colors
colors = child_colors
else:
colors |= child_colors
else:
colors = None
if colors:
self.result += 1
return colors
dfs(0, -1)
return self.result
def check_intersection(self, colors, child_colors):
if len(colors) < len(child_colors):
for c in colors:
if c in child_colors:
return True
else:
for c in child_colors:
if c in colors:
return True
ob = Solution()
print(ob.solve( [
[1,2],
[0],
[0,3],
[2]
], [1, 2, 1, 1]))输入值
[ [1,2], [0], [0,3], [2] ], [1, 2, 1, 1]输出结果
2