The question is pretty straightforward and could be solved either by DFS or BFS. The BFS approach is more suitable for this question as we can stop the search as soon as we find the first leaf node. Consider this simple tree:
1
/ \
2 3
/
4
/
5
Our DFS approach below will traverse the whole tree but the BFS approach will stop at the 2nd level as it meets the first leaf (3). Note that worst case time complexity for both the approaches is O(n) where n is the no. of nodes in the tree.
DFS
int minDepth(TreeNode* root) {
if (!root)
return 0;
int left = minDepth(root->left);
int right = minDepth(root->right);
return (left == 0 || right == 0) ? left + right + 1: min(left,right) + 1;
}
BFS
Solution by @simkieu
int minDepth(TreeNode* root) {
if (root == NULL) return 0;
queue<TreeNode*> Q;
Q.push(root);
int i = 0;
while (!Q.empty()) {
i++;
int k = Q.size();
for (int j=0; j<k; j++) {
TreeNode* rt = Q.front();
if (rt->left) Q.push(rt->left);
if (rt->right) Q.push(rt->right);
Q.pop();
if (rt->left==NULL && rt->right==NULL) return i;
}
}
return -1; //For the compiler thing. The code never runs here.
}