美文网首页一起来刷算法题
minimum-depth-of-binary-tree

minimum-depth-of-binary-tree

作者: cherryleechen | 来源:发表于2019-05-08 14:02 被阅读0次

    时间限制:1秒 空间限制:32768K

    题目描述

    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.

    我的代码

    class Solution {
    public:
        int run(TreeNode *root) {
            if(root==nullptr)
                return 0;
            int left=run(root->left);
            int right=run(root->right);
            if(left*right==0)
                return 1+left+right;
            return 1+min(left,right);
        }
    };
    

    运行时间:13ms
    占用内存:888k

    class Solution {
    public:
        int run(TreeNode *root) {
            if(root==nullptr)
                return 0;
            int count=0;
            deque<TreeNode*> q1;
            q1.push_back(root);
            deque<TreeNode*> q2;
            while(!q1.empty()){
                count+=1;
                q2=q1;q1.clear();
                while(!q2.empty()){
                    TreeNode* cur=q2.front();
                    q2.pop_front();
                    if(cur->left==nullptr && cur->right==nullptr)
                        return count;
                    if(cur->left)
                        q1.push_back(cur->left);
                    if(cur->right)
                        q1.push_back(cur->right);
                }
            }
            return count;
        }
    };
    

    运行时间:14ms
    占用内存:888k

    相关文章

      网友评论

        本文标题:minimum-depth-of-binary-tree

        本文链接:https://www.haomeiwen.com/subject/zhhloqtx.html