在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