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

翻譯

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

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

原文

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;
    }
};