时间限制: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
网友评论