LeetCode 111 Minimum Depth of Binary Tree（二叉樹的最短深度）（BT、DFS）（*）

版權聲明：轉載請聯系本人，感謝配合！本站位址：http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50572933

翻譯

給定一個二叉樹，找出它的最短深度。

最短深度是指從節點到最近的葉節點的最短距離。           

原文

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.           

分析

我以為題意已經很明了了 ，想起來之前的一篇部落格中寫過一個用于求二叉樹高度的函數。

LeetCode 110 Balanced Binary Tree（平衡二叉樹）（*）

想着就拿來直接用了。

下面這代碼是求的節點到所有葉子的最大距離，為了符合本題是以我把最下面的max已經改成了min。

int getHeight(TreeNode* root) {
    int left = 0, right = 0;
    if (!root || (!root->left &&!root->right))
        return 0;
    if (root->left != NULL)
        left = 1 + getHeight(root->left);
    if (root->right != NULL)
        right = 1 + getHeight(root->right);
    return min(left, right);
}           

由于上面的函數算出來的距離是不包括root本身的，是以再使用的時候要加1。

int minDepth(TreeNode* root) {
    if (!root) return 0;
    return getHeight(root)+1;
}           

然而，當我送出之外發現錯了……對于[1,2]，也就是根節點是1，左子樹是2，期望傳回2，而我傳回了1。

納悶了，從右邊上去不就好了？好吧，可能題意是指的隻能從葉子開始走，那麼對于一邊空一邊非空的情況，我們就要求的是最大值了。

比如這樣的話，也是應該傳回3了，從左邊上去才行。

1
    /
   2
  /
 3           

那麼對代碼修改一下：

int getHeight(TreeNode* root) {
    int left = 0, right = 0;
    if (!root || (!root->left && !root->right)) return 0;
    if (root->left &&  root->right) {
        left = getHeight(root->left) + 1;
        right = getHeight(root->right) + 1;
        return min(left, right);
    }
    else {
        left = getHeight(root->left) + 1;
        right = getHeight(root->right) + 1;
        return max(left, right);
    }
}


int minDepth(TreeNode* root) {
    if (!root) return 0;
    return getHeight(root)+1;
}           

好吧，其實我發現left和right這兩個變量可以去掉了：

int getHeight(TreeNode* root) {
    if (!root || (!root->left && !root->right)) return 0;
    if (root->left &&  root->right) return min(getHeight(root->left) + 1, getHeight(root->right) + 1);
    else return max(getHeight(root->left) + 1, getHeight(root->right) + 1);
}

int minDepth(TreeNode* root) {
    if (!root) return 0;
    return getHeight(root) + 1;
}           

其實吧，我還發現在max或min函數内部對兩個參數進行+1操作，完全可以把+1放到外面這樣還隻用加一次了。繼續改：

int getHeight(TreeNode* root) {
    if (!root || (!root->left && !root->right)) return 0;
    if (root->left &&  root->right) return min(getHeight(root->left), getHeight(root->right)) + 1;
    else return max(getHeight(root->left), getHeight(root->right)) + 1;
}

int minDepth(TreeNode* root) {
    if (!root) return 0;
    return getHeight(root) + 1;
}           

然後我就發現，根本沒必要獨立寫一個getHeight函數啦，放到一起，一個深搜算法就出來了，妥妥的……

int minDepth(TreeNode* root) {
    if (!root) return 0;
    if (root->left &&  root->right) return min(minDepth(root->left), minDepth(root->right)) + 1;
    return max(minDepth(root->left), minDepth(root->right)) + 1;
}           

可能有讀者覺得我啰嗦……不過我覺得這樣更好一些，之是以熱愛程式設計，就是因為喜歡自己寫的算法和APP可以不斷的演變，不斷變得更加簡潔好用。

代碼

/**
* 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) return 0;
        if (root->left &&  root->right) return min(minDepth(root->left), minDepth(root->right)) + 1;
        return max(minDepth(root->left), minDepth(root->right)) + 1;
    }
};