Minimum Depth of Binary Tree

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.

C++版：

#include <iostream>

using namespace std;
struct TreeNode {
   int val;
   TreeNode *left;
   TreeNode *right;
   TreeNode(int x):val(x),left(NULL),right(NULL) {}
};

class Solution {
public:
     int minDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(root)
        {
            if(root->left == NULL && root->right == NULL)
                return 1;
            else if(root->left == NULL)
                return minDepth(root->right) + 1;
            else if(root->right == NULL)
                return minDepth(root->left) + 1;
            return min(minDepth(root->left), minDepth(root->right)) + 1;
        }
        return 0;

    }
};

int main(){
    TreeNode *a = new TreeNode(1);
    TreeNode *b = new TreeNode(2);
    TreeNode *c = new TreeNode(3);
    TreeNode *d = new TreeNode(4);
    TreeNode *e = new TreeNode(5);
    TreeNode *f = new TreeNode(6);
    TreeNode *g = new TreeNode(7);

    a->left = b;
    a->right = c;
    b->left = d;
    b->right = e;
    c->left = f;
    c->right = g;
    Solution s1;
    int s = s1.minDepth(a);
    cout<<"the minDepth of the tree is:"<<s<<endl;
    return 0;
}

　　Java版：

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if( root == null) {
            return 0;
        }
        
        LinkedList<TreeNode> nodes = new LinkedList<TreeNode>();
        LinkedList<Integer> counts = new LinkedList<Integer>();
        
        nodes.add(root);
        counts.add(1);
        
        while(!nodes.isEmpty()) {
            TreeNode curr = nodes.remove();
            int count = counts.remove();
            
            if(curr.left != null) {
                nodes.add(curr.left);
                counts.add(count + 1);
            }
            
            if(curr.right != null) {
                nodes.add(curr.right);
                counts.add(count + 1);
            }
            
            if(curr.left == null && curr.right == null) {
                return count;
            }
        }
        return 0;
    }
}