# Description

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.

# Example

Example 1:

Input: {}
Output: 0

Example 2:

Input:  {1,#,2,3}
Output: 3	
Explanation:
	1
	 \ 
	  2
	 /
	3    
it will be serialized {1,#,2,3}

Example 3:

Input:  {1,2,3,#,#,4,5}
Output: 2	
Explanation: 
      1
     / \ 
    2   3
       / \
      4   5  
it will be serialized {1,2,3,#,#,4,5}

# Solution

和 97・Maximum Depth of Binary Tree - LintCode 很像

# 思路

-   这道题用DFS（深度优先搜索）来解答。我们知道，每个节点的深度与它左右子树的深度有关，且等于其左右子树最大深度值加上 1。

• 递归设计
  • 递归条件（recursive case）: 对于当前节点 root ，我们求出左右子树的深度的最大值，再加 1 表示当前节点的深度，返回该数值，即为以 root 为根节点的树的最大深度。
  • 终止条件（base case）：当前节点为空时，认为树深为 0。

# 复杂度分析

• 时间复杂度： O(n) ，其中 n 是节点的数量。我们每个节点只访问一次，因此时间复杂度为 O(n) 。
• 空间复杂度：考虑到递归使用调用栈（call stack）的情况。
  • 最坏情况：树完全不平衡。例如每个节点都只有左节点，此时将递归 n 次，需要保持调用栈的存储为 O(n)
  • 最好情况：树完全平衡。即树的高度为 log(n) ，此时空间复杂度为 O(log(n))

/**

 * Definition of TreeNode:

 * public class TreeNode {

 *     public int val;

 *     public TreeNode left, right;

 *     public TreeNode(int val) {

 *         this.val = val;

 *         this.left = this.right = null;

 *     }

 * }

 */

public class Solution {

    /**

     * @param root: The root of binary tree

     * @return: An integer

     */

    public int minDepth(TreeNode root) {

        if (root == null) return 0;

        int leftDepth = minDepth(root.left);

        int rightDepth = minDepth(root.right);

        // 如果是 {1,#,2,3} 這種葉子都在單邊的 case，一定會是 1 的，因為左邊＝0

        // 所以如果都在單邊，那只算單邊的 depth 就 OK

        if (leftDepth == 0 || rightDepth == 0) {

            return leftDepth + rightDepth + 1;

        }

        return Math.min(leftDepth, rightDepth) + 1;

    }

}