解法一：递归
int minDepth(TreeNode* root)
{
if (root == NULL)
return ; if (root->left == NULL) {
return minDepth(root->right) + ;
} else if (root->right == NULL) {
return minDepth(root->left) + ;
} else {
int left_minDepth = minDepth(root->left);
int right_minDepth = minDepth(root->right);
return left_minDepth < right_minDepth ? left_minDepth + : right_minDepth + ;
}
}
解法二：BFS
int minDepth(TreeNode *root)
{
if (root == NULL)
return ; queue<TreeNode*> node_queue;
node_queue.push(root); int count = ;
while (!node_queue.empty()) {
int len = node_queue.size();
count++;
for (int i = ; i < len; ++i) {
TreeNode *nodeTmp = node_queue.front();
node_queue.pop(); if (nodeTmp->left)
node_queue.push(nodeTmp->left);
if (nodeTmp->right)
node_queue.push(nodeTmp->right);
if (nodeTmp->left == NULL && nodeTmp->right == NULL)
return count;
}
}
}