二叉树的最小深度

---

LeetCode 111

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

解题思路

本题与求二叉树最大深度的思路几乎一样。单独求出左右子树的深度，取两者最小值再加上根节点就是二叉树的最小深度。

值得注意的是，如果样例为[1,2]，左子树深度为1，右子树深度为0，则这棵二叉树的最小深度是2，而不是1。右子树为空，不能算上深度为0的子树，即不存在。所以答案应该按照左子树的深度加上根节点即 1 + 1。

考虑到这点，我们就要单独用条件语句来筛选三种情况。

1.左子树空且右子树不空。return 1 + minDepth(root.right);

2.左子树不空且右子树空。return 1 + minDepth(root.left);

3.左子树和右子树都不空。return Math.min(minDepth(root.left), minDepth(root.right)) + 1;

代码如下

/**
 * 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) {
        if (root == null) {
            return 0;
        } 
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        if (root.left != null && root.right == null) {
            return 1 + leftDepth;
        } else if (root.left == null && root.right != null) {
            return 1 + rightDepth;
        } else {
            return Math.min(leftDepth, rightDepth) + 1;
        }
    }
}