二叉树的最小深度111

需求：

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

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

说明：叶子节点是指没有子节点的节点。
示例1：

二叉树
输入： root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入： root = [2,null,3,null,4,null,5,null,6]
输出： 5

leetcode题目链接

思路

上一篇我们计算了二叉树的最大深度，思路是计算全部的高度即可，那么这里求最小高度是不是我们 获得了左右子节点高度后序最小的那个就可以了呢？
不是的这里要看下高度与深度的概念：
二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）

本题还有一个误区，在处理节点的过程中，最大深度很容易理解，最小深度就不那么好理解，如图：

最小深度

/**
 * 111. 二叉树的最小深度
 */
public class MinDepth111 {

    /**
     * 递归法，相比求MaxDepth要复杂点
     * 因为最小深度是从根节点到最近**叶子节点**的最短路径上的节点数量
     */
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int leftHigh = minDepth(root.left);
        int rightHigh = minDepth(root.right);

        // 左子树为null
        if (root.left == null && root.right != null) {// 左
            return rightHigh + 1;
        }
        // 右子树为null
        if (root.left != null && root.right == null) {// 右
            return leftHigh + 1;
        }

        //左右都不为null
        return Math.min(leftHigh, rightHigh) + 1; // 中
    }

    // 精简后续遍历,很难看出是后续遍历
    public int minDepthJj(TreeNode root) {
        if (root == null) return 0;
        // 左子树为null
        if (root.left == null && root.right != null) {
            return minDepth(root.right) + 1;
        }
        // 右子树为null
        if (root.left != null && root.right == null) {
            return minDepth(root.left) + 1;
        }
        //左右都不为null
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }

    /**
     * 迭代法 层序遍历 广度遍历
     */
    public int minDepthGd(TreeNode root) {
        if (root == null) return 0;
        int high = 0;

        Deque<TreeNode> deque = new LinkedList();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            high++;
            while (size-- > 0) {
                TreeNode node = deque.pop();
                if (node.left != null) deque.offer(node.left);
                if (node.right != null) deque.offer(node.right);
                if (node.left == null && node.right == null) return high;
            }
        }
        return high;
    }
}

验证结果