我正在研究演算法并嘗試解決 LeetCode 問題968。二叉樹相機：
給你
root一棵二叉樹。我們在樹節點上安裝攝像頭，節點上的每個攝像頭都可以監控其父節點、自身及其直接子節點。回傳監視樹的所有節點所需的最小攝像機數。
我被卡住了，在檢查了討論之后，我更好地理解了邏輯，但我仍然在努力理解代碼：
def minCameraCover(self, root):
self.res = 0
def dfs(root):
if not root: return 2
l, r = dfs(root.left), dfs(root.right)
if l == 0 or r == 0:
self.res = 1
return 1
return 2 if l == 1 or r == 1 else 0
return (dfs(root) == 0) self.res
我不明白為什么l, r == 0, 0在 DFS 函式中將基本情況設定為if not root: return 2
這背后的機制是什么使dfs(root.left), def(root.right)回傳 0？
到目前為止，我了解到一個節點具有三種狀態：
- 0：是一片葉子
- 1：有攝像頭，節點是葉子的父節點
- 2：它被蓋住了，但上面沒有攝像頭。
uj5u.com熱心網友回復：
為 a 設定基本情況None，即沒有節點。這樣的虛擬位置從來都不是問題，所以我們可以算作“覆寫”，但那里沒有攝像頭。這就是基本情況回傳 2 的原因。
現在，當遇到葉節點時，顯然兩個遞回呼叫都將None作為引數并回傳 2。
然后運算式2 if l == 1 or r == 1 else 0將計算為 0，因為既不是 1l也不r是 1（它們是 2）：else子句開始了。
我希望這可以澄清葉節點的回傳值將為 0，但對于其他節點也可能發生這種情況：每次遞回呼叫都回傳 2，呼叫者本身將回傳 0。
因此，對這三種狀態的更好解釋是：
- 1：節點有攝像頭
- 2：節點沒有攝像頭，但從下方被覆寫
- 0：節點還沒有攝像頭，不從下方覆寫。如果它有一個父節點，那么該父節點應該有一個攝像頭來覆寫這個節點。它是根，它必須自己有一個相機。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/523491.html
上一篇：將資料從一個表拆分到另一個表
下一篇：查找序列中的第n個項