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.
Analysis:
Both DFS and BFS can work for this problem. Since the aim is to find the shortest path, BFS might be a better idea. A queue is used to save every node from the binary tree in depth order. Pop each node, and push its left child and right child (if exist). If the current node is the leaf node (no left and right children), return its depth. To store the depth of each node, we can use a pair structure <TreeNode* int>.
Note:
pair<TreeNode*, int> is a good data structure to save the node as well as its depth.
int minDepth(TreeNode *root) { // Start typing your C/C++ solution below // DO NOT write int main() function queue< pair<TreeNode*,int> > q; int i=0; if (!root){return 0;} q.push(make_pair(root,1)); while(!q.empty()){ pair<TreeNode*,int> cur = q.front(); q.pop(); if (!cur.first->left && !cur.first->right){ return cur.second; } if(cur.first->left){ q.push(make_pair(cur.first->left,cur.second+1)); } if(cur.first->right){ q.push(make_pair(cur.first->right,cur.second+1)); } } }