MENU

LeetCode111. Minimum Depth of Binary Tree(二叉树 / 搜索)

2019 年 03 月 07 日 • 阅读: 1534 • LeetCode阅读设置

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日 星期四