LeetCode111. Minimum Depth of Binary Tree（二叉树 / 搜索）

LeetCode111. Minimum Depth of Binary Tree（链表 / 搜索）

• Easy
• Accepted：275,214
• Submissions：789,211

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.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its minimum depth = 2.

---

链接

https://leetcode.com/problems/minimum-depth-of-binary-tree

题意

给定一棵二叉树，求它的最小深度。即根结点到叶子结点的最短距离。

题解

之前有一道题求最大深度：LeetCode104. Maximum Depth of Binary Tree（二叉树 / 搜索）。

• 使用dfs，对当前结点，如果它的左子树为空，那么就得考虑它的右子树；如果它的右子树为空，那么就得考虑它的左子树，如果都不为空，那么就取左右子树深度的最小值。因为如果恰好有一个子树为空，那么当前结点就不是叶子节点，而深度只能从非空子树中产生。
• 使用bfs，层次遍历，对于当前结点，如果其左子树和右子树都为空，那么直接返回就行了。
• 实际上使用bfs比较好，考虑一颗二叉树，如果它的左子树有100个结点，右子树只有1个结点，那么使用dfs需要遍历101个结点而bfs只需要遍历2个结点。

代码

• Runtime: 16 ms, faster than 99.78% of C++ online submissions for Minimum Depth of Binary Tree.
• Memory Usage: 19.8 MB, less than 58.91% of C++ online submissions for Minimum Depth of Binary Tree.

// dfs

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL)
            return 0;
        int leftMinDepth = minDepth(root->left);
        int rightMinDepth = minDepth(root->right);
        return (leftMinDepth == 0 || rightMinDepth == 0) ? 
                leftMinDepth + rightMinDepth + 1 : min(leftMinDepth, rightMinDepth) + 1;
    }
};

• Runtime: 16 ms, faster than 99.78% of C++ online submissions for Minimum Depth of Binary Tree.
• Memory Usage: 19.6 MB, less than 73.09% of C++ online submissions for Minimum Depth of Binary Tree.

// bfs

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL)
            return 0;
        queue <TreeNode* >q;
        q.push(root);
        int ans = 0;
        while (!q.empty())
        {
            ++ans;
            int n = q.size();
            for (int i = 0; i < n; ++i)
            {
                TreeNode* p = q.front();
                q.pop();
                if (p->left == NULL && p->right == NULL)
                    return ans;
                if (p->left != NULL)
                    q.push(p->left);
                if (p->right != NULL)
                    q.push(p->right);
            }
        }
        return 0; // can not reach
    }
};

参考

https://leetcode.com/problems/minimum-depth-of-binary-tree/discuss/36045

---

The end.
2019年3月7日 星期四