P16 二叉树的最小深度

描述#

这个题目说的是，给你一棵二叉树，你要找到从根节点到最近的叶子节点的深度。

比如说，给你的二叉树是：
 1

/   

2     4
/ 

8  16
这棵树有 3 个叶子节点，分别是 2，8，16。最近的叶子节点是 2，根节点到 2 共有两个节点，因此最小深度是 2。
再比如说，给你的二叉树是：
1


2


4
这棵树唯一的叶子节点是 4，根节点到它共有 3 个节点，因此最小深度是 3。

代码#

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: (n)
  public int minDepth(TreeNode root) {
    if (root == null) return 0;
    if (root.left == null && root.right == null) return 1;
    if (root.left == null) return minDepth(root.right) + 1;
    if (root.right == null) return minDepth(root.left) + 1;
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
  }

  // Time: O(n), Space: O(n)
  public int minDepthIterative(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    int depth = 1;

    while (!q.isEmpty()) {
      int size = q.size();
      for (int i = 0; i < size; ++i) {
        TreeNode s = q.poll();
        if (s.left == null && s.right == null) return depth;
        if (s.left != null) q.add(s.left);
        if (s.right != null) q.add(s.right);
      }
      ++depth;
    }

    return -1;
  }

}