Leetcode 111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

题意：求一棵二叉树的最小高度(深度)。

思路：
104题是求最大高度，本题是求最小高度，解法是大致相同的。
用分治的方法求非叶子节点左右子树的最小高度。
考虑到[1,null,2]这种二叉树，左子树是空，如果空树返回的高度是0，求左右子树最小高度的时候，0比1小，会有bug。所以递归求解的时候，先判断左右节点是否是null。

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    return helper(root);
}

public int helper(TreeNode root) {
    int min = Integer.MAX_VALUE;
    if (root.left != null) {
        int left = helper(root.left);
        min = Math.min(min, left);
    }
    if (root.right != null) {
        int right = helper(root.right);
        min = Math.min(min, right);
    }

    return min == Integer.MAX_VALUE ? 1 : 1 + min;
}

翻看discuss，排名最高的解法对null节点直接返回0，通过一个left == 0 || right == 0的判断，即可知道要如何返回的最小高度，解法非常简练！

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