求二叉树的最小深度(minimum-depth-of-binary-tree)

Leetcode刷题记录一
求二叉树的最小深度(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.

class Solution {
public:
    int run(TreeNode *root) {
        if(root==NULL) return 0;
        if(root->right == NULL && root->left == NULL) return 1;
        queue<TreeNode* > qu;
        qu.push(root);
        int level = 1;
        while(!qu.empty()){
         int size = qu.size();
         for(int i =0;i<size;i++)
         {
             TreeNode* node = qu.front(); 
             qu.pop();
             if(node->left==NULL && node->right == NULL)return level;
             if(node->left!=NULL)qu.push(node->left);
             if(node->right!=NULL) qu.push(node->right);        
         }
            level++;      
        }
        return level;    
    }
};

利用一个队列遍历二叉树,当遇到某层的某个节点其左右孩子都为NULL时候返回当前的层数,即为所求二叉数的最小深度；否则将当前的节点的左右孩子入队，重新遍历队列。当队列为空时候表明，当前层数的节点已经遍历完了，需要将 层数加一，即到新的一层遍历节点。