监控二叉树
思路
這道題目首先要想，如何放置，才能讓攝像頭數(shù)最小呢？
然后我們發(fā)現(xiàn)題目示例中的攝像頭都沒(méi)有放在葉子節(jié)點(diǎn)上！
這是很重要的一個(gè)線(xiàn)索，攝像頭可以覆蓋上中下三層，如果把攝像頭放在葉子節(jié)點(diǎn)上，就浪費(fèi)的一層的覆蓋。
所以把攝像頭放在葉子節(jié)點(diǎn)的父節(jié)點(diǎn)位置，才能充分利用攝像頭的覆蓋面積。
為什么不從頭結(jié)點(diǎn)開(kāi)始看起呢，為啥要從葉子節(jié)點(diǎn)看呢？
因?yàn)轭^結(jié)點(diǎn)放不放攝像頭也就省下一個(gè)攝像頭， 葉子節(jié)點(diǎn)放不放攝像頭省下了的攝像頭數(shù)量是指數(shù)級(jí)別的。
所以我們要從下往上看，局部最優(yōu)：讓葉子節(jié)點(diǎn)的父節(jié)點(diǎn)安攝像頭，所用攝像頭最少，整體最優(yōu)：全部攝像頭數(shù)量所用最少！
局部最優(yōu)推出全局最優(yōu)，找不出反例，那么就按照貪心來(lái)！
此時(shí)，大體思路就是從下到上，先給葉子節(jié)點(diǎn)父節(jié)點(diǎn)放個(gè)攝像頭，然后隔兩個(gè)節(jié)點(diǎn)放一個(gè)攝像頭，直至到二叉樹(shù)頭結(jié)點(diǎn)。
此時(shí)這道題目還有兩個(gè)難點(diǎn)：
二叉樹(shù)的遍歷
如何隔兩個(gè)節(jié)點(diǎn)放一個(gè)攝像頭
確定遍歷順序
在二叉樹(shù)中如何從下向上推導(dǎo)呢？
可以使用后序遍歷也就是左右中的順序，這樣就可以在回溯的過(guò)程中從下到上進(jìn)行推導(dǎo)了。
int traversal(TreeNode* cur) {// 空節(jié)點(diǎn)，該節(jié)點(diǎn)有覆蓋if (終止條件) return ;int left = traversal(cur->left); // 左int right = traversal(cur->right); // 右邏輯處理 // 中return ;}以上代碼中我們?nèi)×俗蠛⒆雍陀液⒆拥姆祷刂?#xff0c;即left 和 right， 方便以后推導(dǎo)中間節(jié)點(diǎn)的狀態(tài)。
如何隔兩個(gè)節(jié)點(diǎn)放一個(gè)攝像頭
此時(shí)需要狀態(tài)轉(zhuǎn)移。
這個(gè)狀態(tài)應(yīng)該如何轉(zhuǎn)移，我們首先看看每個(gè)節(jié)點(diǎn)可能有幾種狀態(tài)：
1、本節(jié)點(diǎn)無(wú)覆蓋
2、本節(jié)點(diǎn)有攝像頭
3、本節(jié)點(diǎn)有覆蓋
我們分別有三個(gè)數(shù)字來(lái)表示：
0：本節(jié)點(diǎn)無(wú)覆蓋
1：本節(jié)點(diǎn)有攝像頭
2：本節(jié)點(diǎn)有覆蓋
注意：本節(jié)點(diǎn)無(wú)攝像頭，其實(shí)無(wú)攝像頭就是 無(wú)覆蓋 或者 有覆蓋的狀態(tài)，所以一共還是三個(gè)狀態(tài)。
那么在遍歷樹(shù)的過(guò)程中，就會(huì)遇到空節(jié)點(diǎn)，那么問(wèn)題來(lái)了，空節(jié)點(diǎn)究竟是哪一種狀態(tài)呢？空節(jié)點(diǎn)表示無(wú)覆蓋？表示有攝像頭？還是有覆蓋呢？
回歸本質(zhì)，為了讓攝像頭數(shù)量最少，我們要盡量讓葉子節(jié)點(diǎn)的父節(jié)點(diǎn)安裝攝像頭，這樣才能攝像頭的數(shù)量最少。
那么空節(jié)點(diǎn)不能是無(wú)覆蓋的狀態(tài)，這樣葉子節(jié)點(diǎn)就要放攝像頭了，空節(jié)點(diǎn)也不能是有攝像頭的狀態(tài)，這樣葉子節(jié)點(diǎn)的父節(jié)點(diǎn)就沒(méi)有必要放攝像頭了，而是可以把攝像頭放在葉子節(jié)點(diǎn)的爺爺節(jié)點(diǎn)上。
所以空節(jié)點(diǎn)的狀態(tài)只能是有覆蓋，這樣就可以在葉子節(jié)點(diǎn)的父節(jié)點(diǎn)放攝像頭了
接下來(lái)就是遞推關(guān)系。
那么遞歸的終止條件應(yīng)該是遇到了空節(jié)點(diǎn)，此時(shí)應(yīng)該返回2（有覆蓋），原因上面已經(jīng)解釋過(guò)了。
// 空節(jié)點(diǎn)，該節(jié)點(diǎn)有覆蓋 if (cur == NULL) return 2;單層邏輯處理
主要有如下四類(lèi)情況：
情況1：左右節(jié)點(diǎn)都有覆蓋
左孩子有覆蓋，右孩子有覆蓋，那么此時(shí)中間節(jié)點(diǎn)應(yīng)該就是無(wú)覆蓋的狀態(tài)了。
情況2：左右節(jié)點(diǎn)至少有一個(gè)無(wú)覆蓋的情況
如果是以下情況，則中間節(jié)點(diǎn)（父節(jié)點(diǎn)）應(yīng)該放攝像頭：
left == 0 && right == 0 左右節(jié)點(diǎn)無(wú)覆蓋
left == 1 && right == 0 左節(jié)點(diǎn)有攝像頭，右節(jié)點(diǎn)無(wú)覆蓋
left == 0 && right == 1 左節(jié)點(diǎn)有無(wú)覆蓋，右節(jié)點(diǎn)攝像頭
left == 0 && right == 2 左節(jié)點(diǎn)無(wú)覆蓋，右節(jié)點(diǎn)覆蓋
left == 2 && right == 0 左節(jié)點(diǎn)覆蓋，右節(jié)點(diǎn)無(wú)覆蓋
這個(gè)不難理解，畢竟有一個(gè)孩子沒(méi)有覆蓋，父節(jié)點(diǎn)就應(yīng)該放攝像頭。
此時(shí)攝像頭的數(shù)量要加一，并且return 1，代表中間節(jié)點(diǎn)放攝像頭
if (left == 0 || right == 0) {result++;return 1; }情況3：左右節(jié)點(diǎn)至少有一個(gè)有攝像頭
如果是以下情況，其實(shí)就是 左右孩子節(jié)點(diǎn)有一個(gè)有攝像頭了，那么其父節(jié)點(diǎn)就應(yīng)該是2（覆蓋的狀態(tài)）
left == 1 && right == 2 左節(jié)點(diǎn)有攝像頭，右節(jié)點(diǎn)有覆蓋
left == 2 && right == 1 左節(jié)點(diǎn)有覆蓋，右節(jié)點(diǎn)有攝像頭
left == 1 && right == 1 左右節(jié)點(diǎn)都有攝像頭
情況4：頭結(jié)點(diǎn)沒(méi)有覆蓋
以上都處理完了，遞歸結(jié)束之后，可能頭結(jié)點(diǎn) 還有一個(gè)無(wú)覆蓋的情況，如圖：
所以遞歸結(jié)束之后，還要判斷根節(jié)點(diǎn)，如果沒(méi)有覆蓋，result++，代碼如下：
最后的代碼
// 版本一 class Solution { private:int result;int traversal(TreeNode* cur) {// 空節(jié)點(diǎn)，該節(jié)點(diǎn)有覆蓋if (cur == NULL) return 2;int left = traversal(cur->left); // 左int right = traversal(cur->right); // 右// 情況1// 左右節(jié)點(diǎn)都有覆蓋if (left == 2 && right == 2) return 0;// 情況2// left == 0 && right == 0 左右節(jié)點(diǎn)無(wú)覆蓋// left == 1 && right == 0 左節(jié)點(diǎn)有攝像頭，右節(jié)點(diǎn)無(wú)覆蓋// left == 0 && right == 1 左節(jié)點(diǎn)有無(wú)覆蓋，右節(jié)點(diǎn)攝像頭// left == 0 && right == 2 左節(jié)點(diǎn)無(wú)覆蓋，右節(jié)點(diǎn)覆蓋// left == 2 && right == 0 左節(jié)點(diǎn)覆蓋，右節(jié)點(diǎn)無(wú)覆蓋if (left == 0 || right == 0) {result++;return 1;}// 情況3// left == 1 && right == 2 左節(jié)點(diǎn)有攝像頭，右節(jié)點(diǎn)有覆蓋// left == 2 && right == 1 左節(jié)點(diǎn)有覆蓋，右節(jié)點(diǎn)有攝像頭// left == 1 && right == 1 左右節(jié)點(diǎn)都有攝像頭// 其他情況前段代碼均已覆蓋if (left == 1 || right == 1) return 2;// 以上代碼我沒(méi)有使用else，主要是為了把各個(gè)分支條件展現(xiàn)出來(lái)，這樣代碼有助于讀者理解// 這個(gè) return -1 邏輯不會(huì)走到這里。return -1;}public:int minCameraCover(TreeNode* root) {result = 0;// 情況4if (traversal(root) == 0) { // root 無(wú)覆蓋result++;}return result;} };本題的難點(diǎn)首先是要想到貪心的思路，然后就是遍歷和狀態(tài)推導(dǎo)。
總結(jié)
