// Path: src/commons/datastructures/TreeNode.java
// public class TreeNode {
//     public int val;
//     public TreeNode left;
//     public TreeNode right;
//     public TreeNode(int x) {
//         val = x;
//     }
// 
//     @Override
//     public String toString() {
//         return "TreeNode{" +
//                 "val=" + val +
//                 '}';
//     }
// }


import commons.datastructures.TreeNode;
package MinimumDepthofBinaryTree;


/**
 * User: Danyang
 * Date: 1/27/2015
 * Time: 15:11
 *
 * 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.

 */
public class Solution {
    /**
     * Notice:
     * 1. must be leaf node
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        if(root==null)
            return 0;
        return getDepth(root, 1);
    }

    int getDepth(TreeNode cur, int depth) {
        if(cur==null)
            return Integer.MAX_VALUE;
        if(cur.left==null && cur.right==null)
// Path: src/commons/datastructures/TreeNode.java
// public class TreeNode {
//     public int val;
//     public TreeNode left;
//     public TreeNode right;
//     public TreeNode(int x) {
//         val = x;
//     }
// 
//     @Override
//     public String toString() {
//         return "TreeNode{" +
//                 "val=" + val +
//                 '}';
//     }
// }


// Path: src/MinimumDepthofBinaryTree/Solution.java
import commons.datastructures.TreeNode;

package MinimumDepthofBinaryTree;


/**
 * User: Danyang
 * Date: 1/27/2015
 * Time: 15:11
 *
 * 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.

 */
public class Solution {
    /**
     * Notice:
     * 1. must be leaf node
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        if(root==null)
            return 0;
        return getDepth(root, 1);
    }

    int getDepth(TreeNode cur, int depth) {
        if(cur==null)
            return Integer.MAX_VALUE;
        if(cur.left==null && cur.right==null)
            return depth;