資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
