树、递归、广度优先搜索（BFS）————二叉树的最小深度

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int minDepth(TreeNode* root) {
13         if(root==NULL) return 0;//root节点是空节点，深度为0
14         int a=1;
15         if(!root->right && !root->left) return 1;//只有一个节点，深度就是1
16         if(!root->left){//左节点空，右节点非空，在右子树里面找最近的叶子节点
17             return 1+minDepth(root->right);
18         }
19         if(!root->right){//右节点空，左节点非空，在左子树里面找最近的叶子节点
20             return 1+minDepth(root->left);
21         }
22         //两个节点都非空，那就继续迭代下一层
23         return 1+min(minDepth(root->left),minDepth(root->right));
24     }
25 };

 1 class Solution {
 2 public:
 3     int minDepth(TreeNode* root) {
 4         if(root==NULL) return 0;  //判空
 5         queue<pair<TreeNode*,int>> que;  //把节点和所在的层数绑定
 6         que.push(make_pair(root,1)); //压入根节点，层数为1
 7         while(1)
 8         {
 9             TreeNode* node=que.front().first; //当前节点
10             int level=que.front().second;  //层数
11             que.pop();
12             if (!node->left && !node->right) return level;//遇到叶子节点
13             if(node->left) //压入左节点
14                 que.push(make_pair(node->left,level+1));
15             if(node->right)//压入右节点
16                 que.push(make_pair(node->right,level+1));
17         }
18     }
19 };