[[361051]]

監控二叉樹題目地址 : https://leetcode-cn.com/problems/binary-tree-cameras/

給定一個二叉樹，我們在樹的節點上安裝攝像頭。

節點上的每個攝影頭都可以監視其父對象、自身及其直接子對象。

計算監控樹的所有節點所需的最小攝像頭數量。

示例 1：

 

輸入：[0,0,null,0,0]

輸出：1

解釋：如圖所示，一臺攝像頭足以監控所有節點。

示例 2：

 

輸入：[0,0,null,0,null,0,null,null,0]

輸出：2

解釋：需要至少兩個攝像頭來監視樹的所有節點。上圖顯示了攝像頭放置的有效位置之一。

提示：

• 給定樹的節點數的范圍是 [1, 1000]。
• 每個節點的值都是 0。

思路

這道題目首先要想，如何放置，才能讓攝像頭最小的呢?

從題目中示例，其實可以得到啟發，我們發現題目示例中的攝像頭都沒有放在葉子節點上!

這是很重要的一個線索，攝像頭可以覆蓋上中下三層，如果把攝像頭放在葉子節點上，就浪費的一層的覆蓋。

所以把攝像頭放在葉子節點的父節點位置，才能充分利用攝像頭的覆蓋面積。

那么有同學可能問了，為什么不從頭結點開始看起呢，為啥要從葉子節點看呢?

因為頭結點放不放攝像頭也就省下一個攝像頭， 葉子節點放不放攝像頭省下了的攝像頭數量是指數階別的。

所以我們要從下往上看，局部最優：讓葉子節點的父節點安攝像頭，所用攝像頭最少，整體最優：全部攝像頭數量所用最少!

局部最優推出全局最優，找不出反例，那么就按照貪心來!

此時，大體思路就是從低到上，先給葉子節點父節點放個攝像頭，然后隔兩個節點放一個攝像頭，直至到二叉樹頭結點。

此時這道題目還有兩個難點：

1. 二叉樹的遍歷
2. 如何隔兩個節點放一個攝像頭

確定遍歷順序

在二叉樹中如何從低向上推導呢?

可以使用后序遍歷也就是左右中的順序，這樣就可以在回溯的過程中從下到上進行推導了。

后序遍歷代碼如下：

int traversal(TreeNode* cur) { 
 
        // 空節點，該節點有覆蓋 
        if (終止條件) return ; 
 
        int left = traversal(cur->left);    // 左 
        int right = traversal(cur->right);  // 右 
 
        邏輯處理                            // 中 
        return ; 
    } 

注意在以上代碼中我們取了左孩子的返回值，右孩子的返回值，即left 和 right， 以后推導中間節點的狀態

如何隔兩個節點放一個攝像頭

此時需要狀態轉移的公式，大家不要和動態的狀態轉移公式混到一起，本題狀態轉移沒有擇優的過程，就是單純的狀態轉移!

來看看這個狀態應該如何轉移，先來看看每個節點可能有幾種狀態：

有如下三種：

• 該節點無覆蓋
• 本節點有攝像頭
• 本節點有覆蓋

我們分別有三個數字來表示：

• 0：該節點無覆蓋
• 1：本節點有攝像頭
• 2：本節點有覆蓋

大家應該找不出第四個節點的狀態了。

一些同學可能會想有沒有第四種狀態：本節點無攝像頭，其實無攝像頭就是 無覆蓋 或者 有覆蓋的狀態，所以一共還是三個狀態。

因為在遍歷樹的過程中，就會遇到空節點，那么問題來了，空節點究竟是哪一種狀態呢?空節點表示無覆蓋?表示有攝像頭?還是有覆蓋呢?

回歸本質，為了讓攝像頭數量最少，我們要盡量讓葉子節點的父節點安裝攝像頭，這樣才能攝像頭的數量最少。

那么空節點不能是無覆蓋的狀態，這樣葉子節點就要放攝像頭了，空節點也不能是有攝像頭的狀態，這樣葉子節點的父節點就沒有必要放攝像頭了，而是可以把攝像頭放在葉子節點的爺爺節點上。

所以空節點的狀態只能是有覆蓋，這樣就可以在葉子節點的父節點放攝像頭了

接下來就是遞推關系。

那么遞歸的終止條件應該是遇到了空節點，此時應該返回2(有覆蓋)，原因上面已經解釋過了。

代碼如下：

// 空節點，該節點有覆蓋 
if (cur == NULL) return 2; 

遞歸的函數，以及終止條件已經確定了，再來看單層邏輯處理。

主要有如下四類情況：

• 情況1：左右節點都有覆蓋

左孩子有覆蓋，右孩子有覆蓋，那么此時中間節點應該就是無覆蓋的狀態了。

如圖：

 

 

968.監控二叉樹2

 

 

代碼如下：

// 左右節點都有覆蓋 
if (left == 2 && right == 2) return 0; 

• 情況2：左右節點至少有一個無覆蓋的情況

如果是以下情況，則中間節點(父節點)應該放攝像頭：

• left == 0 && right == 0 左右節點無覆蓋
• left == 1 && right == 0 左節點有攝像頭，右節點無覆蓋
• left == 0 && right == 1 左節點有無覆蓋，右節點攝像頭
• left == 0 && right == 2 左節點無覆蓋，右節點覆蓋
• left == 2 && right == 0 左節點覆蓋，右節點無覆蓋

這個不難理解，畢竟有一個孩子沒有覆蓋，父節點就應該放攝像頭。

此時攝像頭的數量要加一，并且return 1，代表中間節點放攝像頭。

代碼如下：

if (left == 0 || right == 0) { 
    result++; 
    return 1; 
} 

• 情況3：左右節點至少有一個有攝像頭

如果是以下情況，其實就是 左右孩子節點有一個有攝像頭了，那么其父節點就應該是2(覆蓋的狀態)

• left == 1 && right == 2 左節點有攝像頭，右節點有覆蓋
• left == 2 && right == 1 左節點有覆蓋，右節點有攝像頭
• left == 1 && right == 1 左右節點都有攝像頭

代碼如下：

if (left == 1 || right == 1) return 2; 

從這個代碼中，可以看出，如果left == 1, right == 0 怎么辦?其實這種條件在情況2中已經判斷過了，如圖：

 

 

968.監控二叉樹1

 

 

這種情況也是大多數同學容易迷惑的情況。

• 情況4：頭結點沒有覆蓋

以上都處理完了，遞歸結束之后，可能頭結點 還有一個無覆蓋的情況，如圖：

 

 

968.監控二叉樹3

 

 

所以遞歸結束之后，還要判斷根節點，如果沒有覆蓋，result++，代碼如下：

int minCameraCover(TreeNode* root) { 
    result = 0; 
    if (traversal(root) == 0) { // root 無覆蓋 
        result++; 
    } 
    return result; 
} 

以上四種情況我們分析完了，代碼也差不多了，整體代碼如下：

(以下我的代碼注釋很詳細，為了把情況說清楚，特別把每種情況列出來。)

C++代碼

// 版本一 
class Solution { 
private: 
    int result; 
    int traversal(TreeNode* cur) { 
 
        // 空節點，該節點有覆蓋 
        if (cur == NULL) return 2; 
 
        int left = traversal(cur->left);    // 左 
        int right = traversal(cur->right);  // 右 
 
        // 情況1 
        // 左右節點都有覆蓋 
        if (left == 2 && right == 2) return 0; 
 
        // 情況2 
        // left == 0 && right == 0 左右節點無覆蓋 
        // left == 1 && right == 0 左節點有攝像頭，右節點無覆蓋 
        // left == 0 && right == 1 左節點有無覆蓋，右節點攝像頭 
        // left == 0 && right == 2 左節點無覆蓋，右節點覆蓋 
        // left == 2 && right == 0 左節點覆蓋，右節點無覆蓋 
        if (left == 0 || right == 0) { 
            result++; 
            return 1; 
        } 
 
        // 情況3 
        // left == 1 && right == 2 左節點有攝像頭，右節點有覆蓋 
        // left == 2 && right == 1 左節點有覆蓋，右節點有攝像頭 
        // left == 1 && right == 1 左右節點都有攝像頭 
        // 其他情況前段代碼均已覆蓋 
        if (left == 1 || right == 1) return 2; 
 
        // 以上代碼我沒有使用else，主要是為了把各個分支條件展現出來，這樣代碼有助于讀者理解 
        // 這個 return -1 邏輯不會走到這里。 
        return -1; 
    } 
 
public: 
    int minCameraCover(TreeNode* root) { 
        result = 0; 
        // 情況4 
        if (traversal(root) == 0) { // root 無覆蓋 
            result++; 
        } 
        return result; 
    } 
}; 

在以上代碼的基礎上，再進行精簡，代碼如下：

// 版本二 
class Solution { 
private: 
    int result; 
    int traversal(TreeNode* cur) { 
        if (cur == NULL) return 2; 
        int left = traversal(cur->left);    // 左 
        int right = traversal(cur->right);  // 右 
        if (left == 2 && right == 2) return 0; 
        else if (left == 0 || right == 0) { 
            result++; 
            return 1; 
        } else return 2; 
    } 
public: 
    int minCameraCover(TreeNode* root) { 
        result = 0; 
        if (traversal(root) == 0) { // root 無覆蓋 
            result++; 
        } 
        return result; 
    } 
}; 

大家可能會驚訝，居然可以這么簡短，其實就是在版本一的基礎上，使用else把一些情況直接覆蓋掉了。

在網上關于這道題解可以搜到很多這種神級別的代碼，但都沒講不清楚，如果直接看代碼的話，指定越看越暈，所以建議大家對著版本一的代碼一步一步來哈，版本二中看不中用!

總結

本題的難點首先是要想到貪心的思路，然后就是遍歷和狀態推導。

在二叉樹上進行狀態推導，其實難度就上了一個臺階了，需要對二叉樹的操作非常嫻熟。

本文轉載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關注。轉載本文請聯系代碼隨想錄公眾號。