尋找二叉樹的最小深度

【T1】

英文題目： Given a binary tree, find its mininum. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

中文題目： 尋找一棵二叉樹的最小深度。最小深度是指從根結點到最近的葉子結點（最短路徑）的節點數。

尋找一棵二叉樹的最小深度。最小深度是指從根結點到最近的葉子結點（最短路徑）的節點數。

先來想一下二叉樹的狀态：

• 先來想想二叉樹的兩種極其簡單的特殊情況：

（1) 若給定的樹是空樹，我們可直接傳回0。

（2）若給定的樹隻有根結點，沒有左右子樹，我們則可直接傳回1。

• 剩下來就是可以考慮稍微複雜的正常情況：

（1）若是隻有右子樹，左子樹為空，那麼我們可以把右子樹當成一個新樹，帶入run()函數，最小深度則是run(右子樹)+1。

（2）若是隻有左子樹，右子樹為空，情況與上類似。

（3）若左右子樹均有，則是左子樹右子樹均計算，将最小的值+1作為原樹的最小深度。

找來了個圖檔舉個例，最小深度的路徑就是1->2：

代碼大緻如下：（不斷的判斷情況加疊代）

class Solution {
public: 
    int run(TreeNode *root) { 
        if(root==NULL){  //空樹
            return 0;
        }
        else if(root->left==NULL && root->right==NULL){  //無左右子樹，隻有根
            return 1;
        }else {   //有左右子樹
            if(root->left==NULL){
                return run(root->right)+1;
            }else if(root->right==NULL){
                return run(root->left)+1;
            }else {
                 return 1+min(run(root->left),run(root->right)); 
            }
            
        }
       return 0;
    } 
};

           

本來是去同學推薦的九度oj，不料關遼，是以選擇在牛客網做了leetcode的題【第一天特意選了基礎題？可我還是送出了n次才過???】,小辣雞終于要開始決定好好使用oj平台體會做題的快樂555，歡迎指正！

–from一個程式設計小渣渣