題目描述：
Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

例子.png

解釋：就是返回所有葉子節(jié)點(diǎn)到根節(jié)點(diǎn)中最短的那條道的長(zhǎng)度

遞歸寫法方法一：

該方法參考博客：https://www.tianmaying.com/tutorial/LC111

這道題目算是一道非常簡(jiǎn)單的題目，我們不妨設(shè)minDepth(t)表示“以t為根節(jié)點(diǎn)的子樹中，所有葉子節(jié)點(diǎn)中深度最小的一個(gè)節(jié)點(diǎn)的深度”，那么我們想要求的答案就是minDepth(root)。

那么如何求解minDepth(t)呢？

我們不妨分情況進(jìn)行討論：

如果t是葉子節(jié)點(diǎn)，即不存在左兒子和右兒子，那么顯然有minDepth(t) = 1。
如果t有左兒子，但是沒有右兒子，那么顯然有minDepth(t) = minDepth(t -> left) + 1。
如果t有右兒子，但是沒有左兒子，那么顯然有minDepth(t) = minDepth(t -> right) + 1。
如果t有兩個(gè)兒子，那么就需要從這兩種方案里面選一個(gè)使得minDepth(t)最小的，即minDepth(t) = min(minDepth(t -> left) + 1, minDepth(t -> right + 1)) = min(minDepth(root -> left), minDepth(root -> right)) + 1。
這樣一來，就將minDepth(t)這個(gè)問題轉(zhuǎn)化成了兩個(gè)規(guī)模較小的問題minDepth(t -> left)和minDepth(t -> right)，從而可以使用遞歸的方法進(jìn)行求解，具體的實(shí)現(xiàn)請(qǐng)參考之后的代碼。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution{
public:
    int minDepth(TreeNode *root){
        if(root == NULL) return 0;
        if(root->left == NULL && root->right == NULL) return 1;
        if(root->left == NULL && root->right != NULL) return minDepth(root->right)+1;
        if(root->right == NULL && root->left != NULL) return minDepth(root->left)+1;
        return min(minDepth(root->right)+1,minDepth(root->left)+1);
          
    }
};

遞歸寫法二

這也是我從網(wǎng)上看來的，無奈忘了出處是哪，在此表示抱歉

思路：
不管什么時(shí)候，左右子樹兩邊都進(jìn)行遞歸計(jì)算樹的深度，返回左右兩邊深度較小的那個(gè)，若某一邊子樹不存在，則認(rèn)為該深度為很大（即此時(shí)返回的是子樹存在的那邊的最小深度）

代碼如下

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution{
public:
    int minDepth(TreeNode *root){
  
         if (root==NULL)return 0;  
         int LDepth=minDepth(root->left);  
         int RDepth=minDepth(root->right);  
          
         if(LDepth==0&&RDepth==0)  
         return 1;  
         if(LDepth==0)  
         LDepth=INT_MAX;  
         if(RDepth==0)  
        RDepth=INT_MAX;  
          
       return min(LDepth,RDepth)+1;  
       
    }
};

其他思路

 可以把每一條路徑都記錄下來，比較出最小的那個(gè)，等我學(xué)會(huì)了c++的list再來寫！