题目

类型：DFS

难度：简单

二叉树的最小深度 - 图1

解题思路

使用深度优先搜索的方法，遍历整棵树，记录最小深度。

对于每一个非叶子节点，只需要分别计算其左右子树的最小叶子节点深度。这样就将一个大问题转化为了小问题，可以递归地解决该问题。

代码

  1. class Solution {
  2.     public int minDepth(TreeNode root) {
  3.         if (root == null) {
  4.             return 0;
  5.         }
  7.         if (root.left == null && root.right == null) {
  8.             return 1;
  9.         }
  11.         int min_depth = Integer.MAX_VALUE;
  12.         if (root.left != null) {
  13.             min_depth = Math.min(minDepth(root.left), min_depth);
  14.         }
  15.         if (root.right != null) {
  16.             min_depth = Math.min(minDepth(root.right), min_depth);
  17.         }
  19.         return min_depth + 1;
  20.     }
  21. }