题目链接

英文链接：https://leetcode.com/problems/minimum-depth-of-binary-tree/

中文链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

题目详述

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

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

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

示例:

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

返回它的最小深度 2.

题目详解

LeetCode104-二叉树的最大深度是求最大深度，本题是求最小深度，思路是一致的。不过，需要注意的是最小深度指的是从根节点到最近叶子节点的最短路径上的节点数量，必须到叶子结点。一个根结点加上一个叶子结点的最小深度是 2，只有根结点的左右孩子均为空最小深度才为 1。问题的症结在于找到叶子节点。

若根结点为 null，则树的深度为 0。
若根结点不为 null，左子树为 null 而右子树不为 null，深度为当前深度加上右子树深度；左子树不为 null 而右子树为 null，深度为当前深度加上左子树深度。
若根结点不为 null，左右子树均为 null，说明这个结点是叶子结点。

例如：

    3
   / \
null  20

上面这个二叉树的最小深度为 2。

递归版：

public class LeetCode_00111 {

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        // 保障一个根结点加上一个叶子结点的最小深度是 2，只有根结点的左右孩子均为空最小深度才为 1
        return leftDepth == 0 || rightDepth == 0 ? 1 + leftDepth + rightDepth : 1 + Math.min(leftDepth, rightDepth);
    }
}

迭代版：运用 DFS，当结点深度大于或等于当前最小深度时，可以剪枝，因为这个结点不可能在构成最小深度的路径上。

public class LeetCode_00111 {

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        ArrayDeque<Pair> stack = new ArrayDeque<>();
        stack.push(new Pair(root, 1));
        int res = Integer.MAX_VALUE;
        while (!stack.isEmpty()) {
            Pair p = stack.pop();
            TreeNode node = p.node;
            int depth = p.depth;
            // 找到叶子结点
            if (node.left == null && node.right == null) {
                res = Math.min(res, depth);
            }
            if (node.left != null && depth + 1 < res) {     // 剪枝
                stack.push(new Pair(node.left, depth + 1));
            }
            if (node.right != null && depth + 1 < res) {    // 剪枝
                stack.push(new Pair(node.right, depth + 1));
            }
        }
        return res;
    }

    static class Pair {
        TreeNode node;
        int depth;

        public Pair(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }
}