题目描述

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。

示例:

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

       3    
      / \   
     9  20    
       /  \    
      15   7

返回它的最小深度  2.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1 – DFS

解法1简单的很，我们就用DFS遍历二叉树，声明一个辅助函数用来遍历private int helper(TreeNode node, int depth)。node是当前节点，depth是当前节点深度。如果当前节点是叶节点，就返回depth；如果node左子树非空，就递归遍历左子树求最小深度；如果node右子树非空，就递归遍历右子树求最小深度，然后取左右子树最小深度的min并返回。

时间复杂度O(n)，空间复杂度O(n)。全部代码如下：

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

        return helper(root, 1);
    }

    private int helper(TreeNode node, int depth) {
        if (node.left == null && node.right == null)
            return depth;

        int minDepth = Integer.MAX_VALUE;

        if (node.left != null)
            minDepth = helper(node.left, depth + 1);

        if (node.right != null)
            minDepth = Math.min(minDepth, helper(node.right, depth + 1));

        return minDepth;
    }
}

解法2 – BFS

解法2用队列实现BFS，但是还需要用一个辅助的Map<TreeNode, Integer>记录节点与它的深度。首先从队列出队一个节点，然后从Map取出该节点深度currLevel。每当下一层的节点入队，就将被入队的节点作为key，currLevel+1作为value存入Map中。当发现出队的节点为叶节点时，就终止BFS过程，返回currLevel作为结果。

BFS遍历的好处是，如果首先碰到了叶节点就可以终止遍历过程。而DFS方式需要遍历所有节点才能够知道最小深度。但是最坏情况下BFS和DFS的时间复杂度是一样的，此外BFS还需要用Map存储节点与深度的对应关系，耗费额外的空间；而访问Map还会有一些开销，因此性能并没有DFS好。

class Solution {
    public int minDepth(TreeNode root) {
        int ans = 0;

        if (root == null)
            return ans;

        Queue<TreeNode> queue = new LinkedList<>();
        Map<TreeNode, Integer> nodeLevel = new HashMap<>();

        queue.offer(root);
        nodeLevel.put(root, 1);

        while (!queue.isEmpty()) {
            root = queue.poll();
            int currLevel = nodeLevel.get(root);

            if (root.left == null && root.right == null) {
                ans = currLevel;
                break;
            }

            if (root.left != null) {
                queue.offer(root.left);
                nodeLevel.put(root.left, currLevel + 1);
            }

            if (root.right != null) {
                queue.offer(root.right);
                nodeLevel.put(root.right, currLevel + 1);
            }
        }

        return ans;
    }
}