主題
題目連結(jié)：
題目意譯：
給定一棵二元樹之根節(jié)點(diǎn) root，我們會(huì)裝設(shè)一些攝影機(jī)在樹中的節(jié)點(diǎn)上。
每個(gè)攝影機(jī)可以監(jiān)測其父母節(jié)點(diǎn)、自己本身以及其直接的子節(jié)點(diǎn)們。
計(jì)算監(jiān)測樹中所有節(jié)點(diǎn)最少所需的攝影機(jī)數(shù)量。
注：
給定的樹中之節(jié)點(diǎn)數(shù)位於範(fàn)圍 [1, 1000] 中。
每個(gè)節(jié)點(diǎn)之值為 0 。
範(fàn)例測資：
範(fàn)例 1：
輸入： [0,0,null,0,0]
輸出： 1
解釋： 一臺(tái)攝影機(jī)便足以監(jiān)測所有節(jié)點(diǎn)，如圖示。
範(fàn)例 2：
輸入： [0,0,null,0,null,0,null,null,0]
輸出： 2
解釋： 至少需要兩臺(tái)攝影機(jī)來監(jiān)測所有節(jié)點(diǎn)。上圖顯示了一種可行的攝影機(jī)之安放。
解題思維：
可以看到，我們基本上不會(huì)在葉節(jié)點(diǎn)（沒有子節(jié)點(diǎn)之節(jié)點(diǎn)）擺放攝影機(jī)。考慮某葉節(jié)點(diǎn)上一層的節(jié)點(diǎn) N（即該葉節(jié)點(diǎn)為該節(jié)點(diǎn)的子節(jié)點(diǎn)），我們可以直接在它的位置擺放攝影機(jī)而不用放在葉節(jié)點(diǎn)。因?yàn)槿绻?N 有第二個(gè)葉節(jié)點(diǎn)，則放在葉節(jié)點(diǎn)的攝影機(jī)等於多放的，放在節(jié)點(diǎn) N 還比較好。
因此我們可以從 root 開始，遞迴左子樹和右子樹（當(dāng)目前節(jié)點(diǎn)為葉節(jié)點(diǎn)時(shí)，則直接回到上一層遞迴）：
如果左右子樹遞迴完後有其中「任何」一者的子樹之根節(jié)點(diǎn)沒有被監(jiān)測到的話，則代表我們需要一臺(tái)攝影機(jī)放在根節(jié)點(diǎn)上監(jiān)測該子樹之根節(jié)點(diǎn)；
而如果左右子樹之根節(jié)點(diǎn)都有被監(jiān)測到，且有其中一個(gè)子樹的根節(jié)點(diǎn)擺著攝影機(jī)，則代表此時(shí)的根節(jié)點(diǎn)將被該攝影機(jī)監(jiān)測到。
而如果左右子樹都有被監(jiān)測且沒有子樹的根節(jié)點(diǎn)放著攝影機(jī)，因此我們可以將此時(shí)的根節(jié)點(diǎn)視為一個(gè)「葉節(jié)點(diǎn)」（因?yàn)閮蓚€(gè)子樹已經(jīng)自主地監(jiān)測了，根節(jié)點(diǎn)不影響兩子樹有沒有被監(jiān)測）。因此其監(jiān)測之策略需交由更上一層的節(jié)點(diǎn)來決定（不過如果剛好是整棵樹的根節(jié)點(diǎn) root，則此時(shí)沒有上一個(gè)節(jié)點(diǎn)，所以應(yīng)放置一臺(tái)攝影機(jī)來監(jiān)測自己）。
所以可以看到每次的遞迴，根節(jié)點(diǎn)會(huì)有三種狀態(tài)：「根節(jié)點(diǎn)需要放攝影機(jī)去監(jiān)測子樹」、「根節(jié)點(diǎn)被其子樹監(jiān)測」、「不知道」。而我們可以將其賦予代號(hào)，例如 1 、 0 、 -1 等等。然後將這個(gè)資訊傳回到上一層遞迴堆疊，來作為上一層之判斷依據(jù)。
而期間我們放的攝影機(jī)數(shù)量即是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
