数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python 中查找树中特殊节点的程序
假设我们有一个名为“tree”的二维列表值，它表示一个 n 叉树，以及另一个名为“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。
要解决此问题，我们将遵循以下步骤 -
result := 0
dfs(0, -1)
return result
定义一个函数 check_intersection()。这将采用 colors、child_colors
如果 (colors) 的长度 < (child_colors) 的长度，则
对于 colors 中的每个 c，执行
如果 c 在 child_colors 中非零，则
返回 True
否则，
对于 child_colors 中的每个 c，执行
如果 c 存在于 child_colors 中，则
返回 True
定义一个函数 dfs()。这将采用 node、prev
colors := {color[node]}
对于 tree[node] 中的每个子节点，执行
如果 child 不等于 prev，则
child_colors := dfs(child, node)
如果 colors 和 child_colors 不为空，则
如果 check_intersection(colors, child_colors) 非零，则
colors := null
否则，
如果 (colors) 的长度 < (child_colors) 的长度，则
child_colors := child_colors OR colors
colors := child_colors
否则，
colors := colors OR child_colors
否则，
colors := null
如果 colors 不为空，则
result := result + 1
return colors
示例
让我们看看以下实现以获得更好的理解 -
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
439 次查看
