Minimum Depth of Binary Tree

题目：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.

思路：深搜+广搜

深搜的方法和之前一样。主要讲一下广搜的方法。

题目最关键的是，使用堆栈的方法，只要我碰到空节点，就返回最终数值，首先一开始就存入根节点，如果空，直接返回，接下来就是弹出节点，如果他没有左右节点，直接返回当前高度，程序很巧妙，每次都是高度加1，这个加1都是由当前层向下一层递进的时候加1的。如果左右节点存在，则存入堆栈。不存在不进行任何操作。

重要的是：最小高度是指从根节点到最近的叶子节点的最小高度，是指没有的叶子节点。也就是说，只要没有孩子了，就返回。

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 //https://leetcode.com/problems/minimum-depth-of-binary-tree/
class Solution1 {
public:
    int minDepth(TreeNode* root) {
        if(root==NULL){
            return 0;
        }
        if(root->left==NULL&&root->right==NULL){
            return 1;
        }

        int left=INT_MAX;
        if(root->left){
            left=minDepth(root->left)+1;
        }

        int right=INT_MAX;
        if(root->right){
            right=minDepth(root->right)+1;
        }
        return min(left,right);
        //如果直接写 return min(minDepth(root->left)+1,minDepth(root->right)+1)这句的话
        //实际上忽略了根节点，一定是从根节点到叶子的最短距离

    }
};

class Solution2 {
public:
    int minDepth(TreeNode* root) {
        return BFS(root);
    }

    int BFS(TreeNode * root){
        if(root==NULL){
            return 0;
        }
        queue<pair<TreeNode*,int> >q;
        q.push(make_pair(root,1));
        while(!q.empty()){
            TreeNode *curNode=q.front().first;
            int curStep=q.front().second;
            q.pop();//这一层结束
            if(curNode->left==NULL&&curNode->right==NULL){
                return curStep;
                //本题的意思就是只要有一层第一个出现空节点就是最小值
            }
            if(curNode->left!=NULL){
                q.push(make_pair(curNode->left,curStep+1));
            }
            if(curNode->right!=NULL){
                q.push(make_pair(curNode->right,curStep+1));
            }
            //本题的巧妙在于我每次都存入一层的节点，当然是没有空的情况下
            //当然题目一开始就判断了，如果下一个节点的左右孩子是空的话，直接返回
        }
    }

};