二叉树的最小深度

题目：二叉树的最小深度

《程序员代码面试指南》第33题 P100 难度：原问题 士★☆☆☆ 进阶问题 将★★★★

本题书上有普通解法和进阶解法。进阶解法用到了遍历二叉树的神级方法——Morris遍历，暂时不看，有空回来补。

下面介绍普通解法。很简单，就是在遍历的过程中去发现所有的叶子结点，并且能够知道该叶子结点的高度。最后找到所有叶子结点高度中的最小值。

牛客上没有这题，力扣上有深度优先搜索和广度优先搜索两种方法。

DFS（时间复杂度O(N)，空间复杂度O(H)）：

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

        if (root.left == null && root.right == null) {
            return 1;
        }

        int min_depth = Integer.MAX_VALUE;
        if (root.left != null) {
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        if (root.right != null) {
            min_depth = Math.min(minDepth(root.right), min_depth);
        }

        return min_depth + 1;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

不难发现，递归直到找到叶子结点后，返回深度1，然后从下往上逐层深度加1，并且每次左子树和右子树取最小深度。到第一层根节点处，同样，找出左子树和右子树的最小深度后，再返回深度加1，即加上根节点的深度，就是整个二叉树的最小深度。

BFS（时间复杂度O(N)，空间复杂度O(N)）：

class Solution {
    class QueueNode {
        TreeNode node;
        int depth;

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

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

        Queue<QueueNode> queue = new LinkedList<QueueNode>();
        queue.offer(new QueueNode(root, 1));
        while (!queue.isEmpty()) {
            QueueNode nodeDepth = queue.poll();
            TreeNode node = nodeDepth.node;
            int depth = nodeDepth.depth;
            if (node.left == null && node.right == null) {
                return depth;
            }
            if (node.left != null) {
                queue.offer(new QueueNode(node.left, depth + 1));
            }
            if (node.right != null) {
                queue.offer(new QueueNode(node.right, depth + 1));
            }
        }

        return 0;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

可以看出，使用了队列的数据结构，每次从队头取出一个节点的同时，将它的左子树和右子树（如果有的话）放入队尾，形成了层序遍历的过程。

对于广度优先搜索进行特别说明：

当找到一个叶子节点时，直接返回这个叶子节点的深度。广度优先搜索的性质保证了最先搜索到的叶子节点的深度一定最小。

这是因为广度优先搜索相当于层序遍历二叉树，如果一个节点是叶子结点，说明当前层和之前的所有层都没有出现过叶子结点（不然就已经返回了），所以第一个搜索到的叶子结点深度一定是最小的。