problem description:
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.
problem analysis:
第一步，设计演算法：遍历一棵树的方法有两种，BFS and DFS，思考了下，BFS是一圈一圈的扩张出去，而这个problem是计算最小的深度，所以BFS可能更适合这个problem。
1.root is the layer 1
2.search out the node in layer 2 by layer1
3.check whether there is a leaf in layer 2: if true, return current layer; if false, continue iteration until finding a leaf.
第二步，设计data structure。在BFS中，优先考虑的data structure是queue，可是在c language中，并没有现成的queue container。那么how to solve this small problem。使用了两个数组，两个index，用来表示数组的长度，这样就实现了一个长度可变的数组。一个数组用来store父节点，另外一个数组用来store孩子节点。当一次iteration结束后，将孩子节点数组的内容移动到父节点数组，孩子节点数组清除为0，在code中，将孩子节点数组的index置为0表示数组当前值无效。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ int minDepth(struct TreeNode* root) { //special case 1 ; //special case 2 ; int numOfParent, numOfChildren; ; ]; ]; //initialization parent[] = root; numOfParent = ; numOfChildren = ; //start iteration from root while(true) { //calculate children ; ; i<numOfParent; i++) { if(parent[i]->left) {children[counter]=parent[i]->left; counter++;} if(parent[i]->right) {children[counter]=parent[i]->right; counter++;} } //store the length of children in numOfChildren, children's level in layer numOfChildren = counter; layer++; //check whether there is a leaf in children ; k<numOfChildren; k++) { if( (children[k]->left==NULL) && (children[k]->right==NULL) ) return layer; } //preparation for next iteration numOfParent = numOfChildren; ; m<numOfChildren; m++) { parent[m] = children[m]; } numOfChildren = ; } }
