111. 二叉树的最小深度

image.png
image.png

递归解法

  1. public class Solution {
  2.     // 可以用 Math.min(左子树的深度，右子树的深度) + 1
  3.     // 但是有一点要注意，当左右子树都不空空的时候是没问题的
  4.     // 但如果左右子树有一个节点为空就会有问题，因为空的那个节点深度是0，不能用这个0作为最小值返回
  5.     // 如果左子树为空则返回右子树的最小深度，右子树同理
  6.     public int minDepth(TreeNode root) {
  7.         // 如果为空返回 0
  8.         if (root == null) return 0;
  10.         // 如果左子树为空，返回右子树的深度
  11.         if (root.left == null)
  12.             return minDepth(root.right) + 1;
  14.         // 如果右子树为空，返回左子树的深度
  15.         if (root.right == null)
  16.             return minDepth(root.left) + 1;
  18.         // 如果左右子树都不为空，返回最小值
  19.         return Math.min(minDepth(root.left) + 1, minDepth(root.right) + 1);
  20.     }
  21. }