LeetCode 111. Minimum Depth of Binary Tree

111. Minimum Depth of Binary Tree（二叉树的最小深度）

链接

https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

题目

给定一个二叉树，找出其最小深度。

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

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

示例:

给定二叉树 [3,9,20,null,null,15,7],

3

/
9 20
/
15 7
返回它的最小深度 2.

思路

二叉树的问题，不过比起最大深度麻烦了不少。
首先还是空节点直接返回0；
如果左右两个子节点有一个为空，最大深度分别为a和b，那么空的那个就应该等于0，返回另外一个深度+0+1；
如果两个都不为空节点，那么返回二者中的较小值+1.
（这题我本来的代码对于[1,2]的结果为1，是错误的，之后参考了题解，才发现我对于题目的理解出了问题）

代码

public class TreeNode {

  int val;
  TreeNode left;
  TreeNode right;

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


public static int minDepth(TreeNode root) {
  if (root == null) {
    return 0;
  }
  if (root.left == null && root.right == null) {
    return 1;
  }
  if (root.left == null || root.right == null) {
    return minDepth(root.right) + minDepth(root.left) + 1;
  }
  return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}