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.

---

解题思路：

方法一： 递归解法，注意如果有个节点只有一边孩子时，不能返回0，要返回另外一半边的depth。 

方法二： BFS, 求layer 的数目，当一个节点没有孩子的时候，返回depth。

---

Java code

方法一： 递归解法

public int minDepth(TreeNode root) {        if(root == null) {            return 0;        }        if(root.left == null && root.right == null) {            return 1;        }        int leftmin = minDepth(root.left);        int rightmin = minDepth(root.right);        if(root.right == null) {            return leftmin + 1;        }        if(root.left == null) {            return rightmin + 1;        }else {            return Math.min(leftmin, rightmin) + 1;        }    }

或者

public int minDepth(TreeNode root) {        if(root == null)            return 0;        int minleft = minDepth(root.left);        int minright = minDepth(root.right);        if(minleft==0 || minright==0)            return minleft>=minright?minleft+1:minright+1;        return Math.min(minleft,minright)+1;    }

方法二： BFS, 求layer 的数目，当一个节点没有孩子的时候，返回depth。

public int minDepth(TreeNode root) {        //use BFS        if(root == null){            return 0;        }        int depth = 1;        LinkedList
     
       queue = new LinkedList
      
       ();        queue.add(root);        int curNum = 1; //num of node left in current level        int nextNum = 0; // num of nodes in next level        while(!queue.isEmpty()){            TreeNode cur = queue.poll();            curNum--;                        if(cur.left == null && cur.right == null) {                return depth;            }            if(cur.left != null) {                queue.add(cur.left);                nextNum++;            }            if(cur.right != null){                queue.add(cur.right);                nextNum++;            }            if(curNum == 0) {                curNum = nextNum;                nextNum = 0;                depth++;            }        }        return depth;        }
      
     

---

20160601

recursion

public class Solution {    public int minDepth(TreeNode root) {        //use recursion every time get min        //base case        if (root == null) {            return 0;        } else if (root.left == null && root.right == null) {            return 1;        }        int num = 0;                if (root.left != null && root.right != null) {            num = Math.min(minDepth(root.left), minDepth(root.right)) + 1;        } else if (root.left == null && root.right != null) {            num = minDepth(root.right) + 1;        } else if (root.left != null && root.right == null) {            num = minDepth(root.left) + 1;        }        return num;    }}

Reference:

1. http://www.cnblogs.com/springfor/p/3879680.html