The application of branch and bound methods in finding the depth of a tree.

reference link:C++ Queue（队列） - 菜鸟教程

reference link: BFS 算法解题套路框架 :: labuladong的算法小抄

The results:

if (tmp ->lchild == NULL && tmp -> rchild == NULL){
            return depth;
        }else{
            if (tmp ->lchild != NULL){
                q.push(tmp ->lchild);
            }
            if(tmp ->rchild != NULL){
                q.push(tmp ->rchild);
            }

The corresponding codes:

// create a binary tree with pre-oder and in-order and return its minimum depth of the tree 
#include <iostream>
#include <vector>
#include <queue>
struct BTNode{
	int data;
	BTNode *lchild;
	BTNode *rchild;
};
using namespace std;
//void fill_pre(vector<int> pre);
//void fill_in(vector<int> in);
BTNode *create_BT(vector<int> pre, vector<int> in);
void post_order_cout(BTNode *root);
int min_depth(BTNode *root);
int main()
{
	vector<int> pre; //the invector variable pre and in is to collect adpatively the data in tree
	pre.push_back(5);  //a function which will fill up the vector pre-oder
	pre.push_back(3);
	pre.push_back(7);
	pre.push_back(6);
	pre.push_back(4);
	//pre.push_back(8);
	//pre.push_back(9); 
	
	vector<int> in;   //a function which will fill up the vector in-oder
	in.push_back(7);
	in.push_back(3);
	in.push_back(6);
	in.push_back(5);
	in.push_back(4);
	//in.push_back(8);
	//in.push_back(9);   
	BTNode *root = create_BT(pre, in); // The function of create_BT using the pre and in is to generate a binary tree
	post_order_cout(root);    // this function is to travel the tree and print it
    cout << "The minimum number of the depth of the tree is : " << min_depth(root) << endl;
	return 0;
}
BTNode *create_BT(vector<int> pre, vector<int> in)
{
	if((pre.size() ==0)||(in.size() == 0)||(pre.size()!=in.size())){     
		return NULL;
	}
	BTNode *root = new BTNode;     //design the root node using the first number in pre-oder vector
	root -> data = pre[0];
	root -> lchild = NULL;
	root -> rchild = NULL;
	
	int index = 0;                // log the position of root node in the in-oder vector
	for(int i=0; i<pre.size(); ++i){
		if(root -> data ==in[i]){
			index = i;
		}
	}
	
	vector<int> leftPre, leftIn, rightPre, rightIn;
 
	for(int i=1; i<=index; ++i){            //generate the pre-oder of sub-left binary tree
		leftPre.push_back(pre[i]);
	}
	for(int i=index+1; i<pre.size(); ++i){   //generate the pre-oder of sub-right binary tree
		rightPre.push_back(pre[i]);
	}
	for(int i=0; i<index; ++i){           //generate the in-oder of sub-left binary tree
		leftIn.push_back(in[i]);	
	}
	for(int i=index+1; i<pre.size(); ++i){  //generate the in-oder of sub-right binary tree
		rightIn.push_back(in[i]);
	}
	root -> lchild = create_BT(leftPre, leftIn);
	root -> rchild = create_BT(rightPre, rightIn);
	return root;
}
void post_order_cout(BTNode *root)
{
	if(root == NULL){
		return;
	}
	post_order_cout(root->lchild);
	post_order_cout(root->rchild);
	cout << "The number is " << root->data <<endl;
}
int min_depth(BTNode *root)
{
    queue<BTNode*> q;
    BTNode *tmp;
    if(root == NULL) return 0;
    int depth = 1;
    q.push(root);
    while (!q.empty()){
         for (int i = 0; i < q.size(); i++){
            tmp = q.front();
             q.pop();
            if (tmp ->lchild == NULL && tmp -> rchild == NULL){
                return ++depth;
            }else{
                if (tmp ->lchild != NULL){
                    q.push(tmp ->lchild);
                }
                if(tmp ->rchild != NULL){
                    q.push(tmp ->rchild);
                }
            }
        }
        depth++;
    }
    return depth;
}