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