專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

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

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

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

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

問題描述

來源：LeetCode第111題

難度：簡單

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

說明：葉子節點是指沒有子節點的節點。

示例1：

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

示例2：

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

• 樹中節點數的范圍在 [0, 10^5] 內

• -1000 <= Node.val <= 1000

問題分析

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

還一種是使用遞歸的方式，如果左子樹為空，則計算右子樹的深度，如果右子樹為空，則計算左子樹的深度，如果左右子樹都不為空，則取左右子樹深度的最小值加 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;     }

筆者簡介

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