二叉树的最小深度

题目描述：给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，返回它的最小深度 2

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public int minDepth(TreeNode root) {

  }
}

方法一：递归

叶子节点的定义是左孩子和右孩子都为 null 时叫做叶子节点，递归结束条件：

当 root 节点左右孩子都为空时，返回 1
当 root 节点左右孩子有一个为空时，返回不为空的孩子节点的深度（注意这个条件，最开始自己写的是 return Math.min(m1, m2) ）
当 root 节点左右孩子都不为空时，返回左右孩子较小深度的节点值

class Solution {
  public int minDepth(TreeNode root) {
    if(root == null) return 0;
    int m1 = minDepth(root.left);
    int m2 = minDepth(root.right);
    //1. 如果左孩子和右孩子有为空的情况，直接返回 m1 + m2 + 1
    //2. 如果都不为空，返回较小深度 + 1
    return root.left == null || root.right == null ? m1 + m2 + 1 : Math.min(m1, m2) + 1;
  }
}

复杂度分析：

时间复杂度：O(N)，其中 N 是树的节点数。对每个节点访问一次。
空间复杂度：O(H)，其中 H 是树的高度。空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为 O(N)。平均情况下树的高度与节点数的对数正相关，空间复杂度为 O(logN)。

执行结果：通过

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.6 MB, 在所有 Java 提交中击败了91.68%的用户

方法二：遍历

当我们找到一个叶子节点时，直接返回这个叶子节点的深度。广度优先搜索的性质保证了最先搜索到的叶子节点的深度一定最小。

class Solution {
  public int minDepth(TreeNode root) {
    if(root == null) return 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int level = 0;
    while(!queue.isEmpty()) {
      level++;
      int size = queue.size();
      while(size > 0) {
        TreeNode node = queue.poll();
        if(node.left == null && node.right == null) return level;
        if(node.left != null) {
          queue.offer(node.left);
        }
        if(node.right != null) {
          queue.offer(node.right);
        }
        size--;
      }
    }
    return level;
  }
}

复杂度分析：

时间复杂度：O(N)，其中 N 是树的节点数。对每个节点访问一次。
空间复杂度：O(N)，其中 N 是树的节点数。空间复杂度主要取决于队列的开销，队列中的元素个数不会超过树的节点数

执行结果：通过

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.6 MB, 在所有 Java 提交中击败了96.13%的用户