專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服
專欄：50多種經(jīng)典圖論算法全部掌握
據(jù)華為內(nèi)部通報(bào)，在外包招聘過程中，多名產(chǎn)品線負(fù)責(zé)人存在自身參與替考、安排別人代考、向候選人泄題等違規(guī)行為；還有多人存在通過出賣公司信息資產(chǎn)獲利的情況。經(jīng)研究，對(duì)涉事人員予以開除，并要求其退回非法獲利、賠償公司損失。
據(jù)網(wǎng)傳聊天截圖顯示，招一個(gè)人可以拿2W內(nèi)推費(fèi)，然后這邊hr說包進(jìn)od。公司這邊幫忙撈人，協(xié)助作弊，有代考，泄題，寫好面評(píng)。入職之后一個(gè)月收兩千，也就是說，每個(gè)外包，至少能薅2萬，如果入職之后，每月還能持續(xù)薅2000元。截圖稱共裁了100多個(gè)od（外包），光內(nèi)推費(fèi)就已經(jīng)超200萬元，而實(shí)際可能更高。
--------------下面是今天的算法題--------------
來看下今天的算法題，這題是LeetCode的第111題：二叉樹的最小深度。
問題描述
來源：LeetCode第111題
難度：簡(jiǎn)單
給定一個(gè)二叉樹，找出其最小深度。最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。
說明：葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例1：
輸入：root = [3,9,20,null,null,15,7] 輸出：2
示例2：
輸入：root = [2,null,3,null,4,null,5,null,6] 輸出：5
樹中節(jié)點(diǎn)數(shù)的范圍在 [0, 10^5] 內(nèi)
-1000 <= Node.val <= 1000
問題分析
這題讓計(jì)算二叉樹的最小深度，也就是從根節(jié)點(diǎn)到最近的葉子節(jié)點(diǎn)，比較簡(jiǎn)單。常見的有兩種實(shí)現(xiàn)方式，一種是使用BFS，也就是一層一層的遍歷，當(dāng)遍歷到第一個(gè)葉子節(jié)點(diǎn)的時(shí)候，它所在的層數(shù)就是二叉樹的最小深度。
還一種是使用遞歸的方式，如果左子樹為空，則計(jì)算右子樹的深度，如果右子樹為空，則計(jì)算左子樹的深度，如果左右子樹都不為空，則取左右子樹深度的最小值加 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; // 如果左右子樹都不為空，返回左右子樹深度最小的那個(gè)+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; // 如果左右子樹都不為空，返回左右子樹深度最小的那個(gè)+1 return min(minDepth(root->left), minDepth(root->right)) + 1; }筆者簡(jiǎn)介
博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號(hào)中寫算法題解800多題，對(duì)算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。
熱門跟貼