在Python中查找树中的特殊节点的程序

假设我们有一个名为“tree”的值的2D列表，它表示一个n叉树和另一个名为“color”的值的列表。树被表示为邻接列表，其根是tree [0]。

第i个节点的特征为−

tree [i]是它的子代和父代。
color [i]是其颜色。

我们称节点N为“ 特殊 ”，如果以N为根的子树中的每个节点都具有唯一的颜色。因此，我们有了这棵树，我们必须找出特殊节点的数量。

因此，如果输入如下：
   tree = [
   [1,2],
   [0],
   [0,3],
   [2]
]

colors = [1, 2, 1, 1]，则输出将为2。

为了解决这个问题，我们将遵循以下步骤−

result：= 0
dfs（0，-1）
返回结果
定义一个函数check_intersection（）。它将获取颜色，child_colors
- 如果（颜色）的长度小于（child_colors）的长度，则
  - 对于颜色中的每个c，执行以下操作：
  - 如果在child_colors中的c不为零，则
    - 返回True
- 否则，
  - 对于child_colors中的每个c，执行以下操作：
  - 如果c存在于child_colors中，则
    - 返回True
定义一个函数dfs（）。它将获取node，prev
- 颜色：= {color [node]}
- 对于tree [node]中的每个child，执行以下操作：
  - 如果child与prev不同，则
  - child_colors：= dfs（child，node）
  - 如果颜色和child_colors都不为空，则
    - 如果check_intersection(颜色，child_colors)不为零，则
    - 颜色：= null
    - 否则，
    - 如果（颜色）的长度小于（child_colors）的长度，则
      - child_colors：= child_colors OR颜色
      - 颜色：= child_colors
    - 否则，
      - 颜色：=颜色OR child_colors
  - 否则，
    - 颜色：= null
  - 如果颜色不为空，则
    - 结果：=结果+1
  - 返回颜色

示例

让我们看以下实现以更好地了解−

“`python 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]))