自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

貪心算法：我要監(jiān)控二叉樹！

作者：程序員Carl
安全 算法
給定一個(gè)二叉樹，我們?cè)跇涞墓?jié)點(diǎn)上安裝攝像頭。節(jié)點(diǎn)上的每個(gè)攝影頭都可以監(jiān)視其父對(duì)象、自身及其直接子對(duì)象。計(jì)算監(jiān)控樹的所有節(jié)點(diǎn)所需的最小攝像頭數(shù)量。

 [[361051]]

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

給定一個(gè)二叉樹，我們?cè)跇涞墓?jié)點(diǎn)上安裝攝像頭。

節(jié)點(diǎn)上的每個(gè)攝影頭都可以監(jiān)視其父對(duì)象、自身及其直接子對(duì)象。

計(jì)算監(jiān)控樹的所有節(jié)點(diǎn)所需的最小攝像頭數(shù)量。

示例 1：

 

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

輸出：1

解釋：如圖所示，一臺(tái)攝像頭足以監(jiān)控所有節(jié)點(diǎn)。

示例 2：

 

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

輸出：2

解釋：需要至少兩個(gè)攝像頭來(lái)監(jiān)視樹的所有節(jié)點(diǎn)。上圖顯示了攝像頭放置的有效位置之一。

提示：

  • 給定樹的節(jié)點(diǎn)數(shù)的范圍是 [1, 1000]。
  • 每個(gè)節(jié)點(diǎn)的值都是 0。

思路

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

從題目中示例，其實(shí)可以得到啟發(fā)，我們發(fā)現(xiàn)題目示例中的攝像頭都沒(méi)有放在葉子節(jié)點(diǎn)上!

這是很重要的一個(gè)線索，攝像頭可以覆蓋上中下三層，如果把攝像頭放在葉子節(jié)點(diǎn)上，就浪費(fèi)的一層的覆蓋。

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

那么有同學(xué)可能問(wèn)了，為什么不從頭結(jié)點(diǎn)開始看起呢，為啥要從葉子節(jié)點(diǎn)看呢?

因?yàn)轭^結(jié)點(diǎn)放不放攝像頭也就省下一個(gè)攝像頭， 葉子節(jié)點(diǎn)放不放攝像頭省下了的攝像頭數(shù)量是指數(shù)階別的。

所以我們要從下往上看，局部最優(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è)攝像頭，直至到二叉樹頭結(jié)點(diǎn)。

此時(shí)這道題目還有兩個(gè)難點(diǎn)：

  1. 二叉樹的遍歷
  2. 如何隔兩個(gè)節(jié)點(diǎn)放一個(gè)攝像頭

確定遍歷順序

在二叉樹中如何從低向上推導(dǎo)呢?

可以使用后序遍歷也就是左右中的順序，這樣就可以在回溯的過(guò)程中從下到上進(jìn)行推導(dǎo)了。

后序遍歷代碼如下：

  1. int traversal(TreeNode* cur) { 
  2.  
  3.         // 空節(jié)點(diǎn)，該節(jié)點(diǎn)有覆蓋 
  4.         if (終止條件) return ; 
  5.  
  6.         int left = traversal(cur->left);    // 左 
  7.         int right = traversal(cur->right);  // 右 
  8.  
  9.         邏輯處理                            // 中 
  10.         return ; 
  11.     } 

注意在以上代碼中我們?nèi)×俗蠛⒆拥姆祷刂?，右孩子的返回值，即left 和 right， 以后推導(dǎo)中間節(jié)點(diǎn)的狀態(tài)

如何隔兩個(gè)節(jié)點(diǎn)放一個(gè)攝像頭

此時(shí)需要狀態(tài)轉(zhuǎn)移的公式，大家不要和動(dòng)態(tài)的狀態(tài)轉(zhuǎn)移公式混到一起，本題狀態(tài)轉(zhuǎn)移沒(méi)有擇優(yōu)的過(guò)程，就是單純的狀態(tài)轉(zhuǎn)移!

來(lái)看看這個(gè)狀態(tài)應(yīng)該如何轉(zhuǎn)移，先來(lái)看看每個(gè)節(jié)點(diǎn)可能有幾種狀態(tài)：

有如下三種：

  • 該節(jié)點(diǎn)無(wú)覆蓋
  • 本節(jié)點(diǎn)有攝像頭
  • 本節(jié)點(diǎn)有覆蓋

我們分別有三個(gè)數(shù)字來(lái)表示：

  • 0：該節(jié)點(diǎn)無(wú)覆蓋
  • 1：本節(jié)點(diǎn)有攝像頭
  • 2：本節(jié)點(diǎn)有覆蓋

大家應(yīng)該找不出第四個(gè)節(jié)點(diǎn)的狀態(tài)了。

一些同學(xué)可能會(huì)想有沒(méi)有第四種狀態(tài)：本節(jié)點(diǎn)無(wú)攝像頭，其實(shí)無(wú)攝像頭就是 無(wú)覆蓋 或者 有覆蓋的狀態(tài)，所以一共還是三個(gè)狀態(tài)。

因?yàn)樵诒闅v樹的過(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ò)了。

代碼如下：

  1. // 空節(jié)點(diǎn)，該節(jié)點(diǎn)有覆蓋 
  2. if (cur == NULL) return 2; 

遞歸的函數(shù)，以及終止條件已經(jīng)確定了，再來(lái)看單層邏輯處理。

主要有如下四類情況：

  • 情況1：左右節(jié)點(diǎn)都有覆蓋

左孩子有覆蓋，右孩子有覆蓋，那么此時(shí)中間節(jié)點(diǎn)應(yīng)該就是無(wú)覆蓋的狀態(tài)了。

如圖：

 

 


968.監(jiān)控二叉樹2

 

 

代碼如下：

  1. // 左右節(jié)點(diǎn)都有覆蓋 
  2. if (left == 2 && right == 2) return 0; 
  • 情況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)放攝像頭。

代碼如下：

  1. if (left == 0 || right == 0) { 
  2.     result++; 
  3.     return 1; 
  4. } 
  • 情況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)都有攝像頭

代碼如下：

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

從這個(gè)代碼中，可以看出，如果left == 1, right == 0 怎么辦?其實(shí)這種條件在情況2中已經(jīng)判斷過(guò)了，如圖：

 

 


968.監(jiān)控二叉樹1

 

 

這種情況也是大多數(shù)同學(xué)容易迷惑的情況。

  • 情況4：頭結(jié)點(diǎn)沒(méi)有覆蓋

以上都處理完了，遞歸結(jié)束之后，可能頭結(jié)點(diǎn) 還有一個(gè)無(wú)覆蓋的情況，如圖：

 

 


968.監(jiān)控二叉樹3

 

 

所以遞歸結(jié)束之后，還要判斷根節(jié)點(diǎn)，如果沒(méi)有覆蓋，result++，代碼如下：

  1. int minCameraCover(TreeNode* root) { 
  2.     result = 0; 
  3.     if (traversal(root) == 0) { // root 無(wú)覆蓋 
  4.         result++; 
  5.     } 
  6.     return result; 
  7. } 

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

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

C++代碼

  1. // 版本一 
  2. class Solution { 
  3. private: 
  4.     int result; 
  5.     int traversal(TreeNode* cur) { 
  6.  
  7.         // 空節(jié)點(diǎn)，該節(jié)點(diǎn)有覆蓋 
  8.         if (cur == NULL) return 2; 
  9.  
  10.         int left = traversal(cur->left);    // 左 
  11.         int right = traversal(cur->right);  // 右 
  12.  
  13.         // 情況1 
  14.         // 左右節(jié)點(diǎn)都有覆蓋 
  15.         if (left == 2 && right == 2) return 0; 
  16.  
  17.         // 情況2 
  18.         // left == 0 && right == 0 左右節(jié)點(diǎn)無(wú)覆蓋 
  19.         // left == 1 && right == 0 左節(jié)點(diǎn)有攝像頭，右節(jié)點(diǎn)無(wú)覆蓋 
  20.         // left == 0 && right == 1 左節(jié)點(diǎn)有無(wú)覆蓋，右節(jié)點(diǎn)攝像頭 
  21.         // left == 0 && right == 2 左節(jié)點(diǎn)無(wú)覆蓋，右節(jié)點(diǎn)覆蓋 
  22.         // left == 2 && right == 0 左節(jié)點(diǎn)覆蓋，右節(jié)點(diǎn)無(wú)覆蓋 
  23.         if (left == 0 || right == 0) { 
  24.             result++; 
  25.             return 1; 
  26.         } 
  27.  
  28.         // 情況3 
  29.         // left == 1 && right == 2 左節(jié)點(diǎn)有攝像頭，右節(jié)點(diǎn)有覆蓋 
  30.         // left == 2 && right == 1 左節(jié)點(diǎn)有覆蓋，右節(jié)點(diǎn)有攝像頭 
  31.         // left == 1 && right == 1 左右節(jié)點(diǎn)都有攝像頭 
  32.         // 其他情況前段代碼均已覆蓋 
  33.         if (left == 1 || right == 1) return 2; 
  34.  
  35.         // 以上代碼我沒(méi)有使用else，主要是為了把各個(gè)分支條件展現(xiàn)出來(lái)，這樣代碼有助于讀者理解 
  36.         // 這個(gè) return -1 邏輯不會(huì)走到這里。 
  37.         return -1; 
  38.     } 
  39.  
  40. public: 
  41.     int minCameraCover(TreeNode* root) { 
  42.         result = 0; 
  43.         // 情況4 
  44.         if (traversal(root) == 0) { // root 無(wú)覆蓋 
  45.             result++; 
  46.         } 
  47.         return result; 
  48.     } 
  49. }; 

在以上代碼的基礎(chǔ)上，再進(jìn)行精簡(jiǎn)，代碼如下：

  1. // 版本二 
  2. class Solution { 
  3. private: 
  4.     int result; 
  5.     int traversal(TreeNode* cur) { 
  6.         if (cur == NULL) return 2; 
  7.         int left = traversal(cur->left);    // 左 
  8.         int right = traversal(cur->right);  // 右 
  9.         if (left == 2 && right == 2) return 0; 
  10.         else if (left == 0 || right == 0) { 
  11.             result++; 
  12.             return 1; 
  13.         } else return 2; 
  14.     } 
  15. public: 
  16.     int minCameraCover(TreeNode* root) { 
  17.         result = 0; 
  18.         if (traversal(root) == 0) { // root 無(wú)覆蓋 
  19.             result++; 
  20.         } 
  21.         return result; 
  22.     } 
  23. }; 

大家可能會(huì)驚訝，居然可以這么簡(jiǎn)短，其實(shí)就是在版本一的基礎(chǔ)上，使用else把一些情況直接覆蓋掉了。

在網(wǎng)上關(guān)于這道題解可以搜到很多這種神級(jí)別的代碼，但都沒(méi)講不清楚，如果直接看代碼的話，指定越看越暈，所以建議大家對(duì)著版本一的代碼一步一步來(lái)哈，版本二中看不中用!

總結(jié)

本題的難點(diǎn)首先是要想到貪心的思路，然后就是遍歷和狀態(tài)推導(dǎo)。

在二叉樹上進(jìn)行狀態(tài)推導(dǎo)，其實(shí)難度就上了一個(gè)臺(tái)階了，需要對(duì)二叉樹的操作非常嫻熟。

本文轉(zhuǎn)載自微信公眾號(hào)「代碼隨想錄」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系代碼隨想錄公眾號(hào)。

 

責(zé)任編輯：武曉燕 來(lái)源： 代碼隨想錄
貪心算法監(jiān)控
相關(guān)推薦

2021-09-29 10:19:00

算法平衡二叉樹

2013-07-15 16:35:55

二叉樹迭代器

2020-04-27 07:05:58

二叉樹左子樹右子樹

2020-09-23 18:25:40

算法二叉樹多叉樹

2021-12-17 14:26:58

二叉樹節(jié)點(diǎn)數(shù)量

2021-09-15 07:56:32

二叉樹層次遍歷

2020-12-22 08:56:51

JavaScript數(shù)據(jù)結(jié)構(gòu)前端

2009-08-11 13:29:57

C#二叉樹遍歷

2021-09-28 06:28:51

二叉樹公共祖先

2021-04-19 07:47:42

數(shù)據(jù)結(jié)構(gòu)二叉樹Tree

2021-04-20 08:37:14

數(shù)據(jù)結(jié)構(gòu)二叉樹樹

2021-03-17 08:19:22

二叉樹LeetCode樹

2021-04-28 20:12:27

數(shù)據(jù)結(jié)構(gòu)創(chuàng)建

2020-11-02 09:15:47

算法與數(shù)據(jù)結(jié)構(gòu)

2021-03-22 08:23:29

LeetCode二叉樹節(jié)點(diǎn)

2021-08-27 11:36:44

二叉樹回溯節(jié)點(diǎn)

2023-05-08 15:57:16

二叉樹數(shù)據(jù)結(jié)構(gòu)

2022-10-26 23:58:02

二叉樹數(shù)組算法

2021-05-06 17:46:30

二叉樹數(shù)據(jù)結(jié)構(gòu)

2021-07-13 14:03:24

二叉樹滿二叉樹完全二叉樹
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)