專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

據(jù)華為內(nèi)部通報，在外包招聘過程中，多名產(chǎn)品線負(fù)責(zé)人存在自身參與替考、安排別人代考、向候選人泄題等違規(guī)行為；還有多人存在通過出賣公司信息資產(chǎn)獲利的情況。經(jīng)研究，對涉事人員予以開除，并要求其退回非法獲利、賠償公司損失。

據(jù)網(wǎng)傳聊天截圖顯示，招一個人可以拿2W內(nèi)推費，然后這邊hr說包進(jìn)od。公司這邊幫忙撈人，協(xié)助作弊，有代考，泄題，寫好面評。入職之后一個月收兩千，也就是說，每個外包，至少能薅2萬，如果入職之后，每月還能持續(xù)薅2000元。截圖稱共裁了100多個od（外包），光內(nèi)推費就已經(jīng)超200萬元，而實際可能更高。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第111題：二叉樹的最小深度。

問題描述

來源：LeetCode第111題

難度：簡單

給定一個二叉樹，找出其最小深度。最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數(shù)量。

說明：葉子節(jié)點是指沒有子節(jié)點的節(jié)點。

示例1：

輸入：root = [3,9,20,null,null,15,7] 輸出：2

示例2：

輸入：root = [2,null,3,null,4,null,5,null,6] 輸出：5

• 樹中節(jié)點數(shù)的范圍在 [0, 10^5] 內(nèi)

• -1000 <= Node.val <= 1000

問題分析

這題讓計算二叉樹的最小深度，也就是從根節(jié)點到最近的葉子節(jié)點，比較簡單。常見的有兩種實現(xiàn)方式，一種是使用BFS，也就是一層一層的遍歷，當(dāng)遍歷到第一個葉子節(jié)點的時候，它所在的層數(shù)就是二叉樹的最小深度。

還一種是使用遞歸的方式，如果左子樹為空，則計算右子樹的深度，如果右子樹為空，則計算左子樹的深度，如果左右子樹都不為空，則取左右子樹深度的最小值加 1 。

JAVA：

public int minDepth(TreeNode root) {     if (root == null)         return 0;     // 如果左子樹等于空，返回右子樹的最小高度+1     if (root.left == null)         return minDepth(root.right) + 1;     // 如果右子樹等于空，返回左子樹的最小高度+1     if (root.right == null)         return minDepth(root.left) + 1;     // 如果左右子樹都不為空，返回左右子樹深度最小的那個+1     return Math.min(minDepth(root.left), minDepth(root.right)) + 1; }

C++：

public:     int minDepth(TreeNode *root) {         if (root == nullptr)             return 0;         // 如果左子樹等于空，返回右子樹的最小高度+1         if (root->left == nullptr)             return minDepth(root->right) + 1;         // 如果右子樹等于空，返回左子樹的最小高度+1         if (root->right == nullptr)             return minDepth(root->left) + 1;         // 如果左右子樹都不為空，返回左右子樹深度最小的那個+1         return min(minDepth(root->left), minDepth(root->right)) + 1;     }

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。