vlambda博客
学习文章列表

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

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

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

这题其实不难，看到这道题我们首先想到的是BFS，就是一层一层的遍历，如果某一层的某个节点没有子节点了，我们就返回这个节点的层数即可。

比如上面的9在第二层，他没有子节点了，我们直接返回他所在的层数2即可，没必要在遍历第3层了。代码很简单，我们来看下。

 1public int minDepth(TreeNode root) {
 2    if (root == null)
 3        return 0;
 4    Queue<TreeNode> queue = new LinkedList<>();
 5    queue.add(root);//入队
 6    int level = 0;
 7    while (!queue.isEmpty()) {//队列不为空就继续循环
 8        level++;
 9        int levelCount = queue.size();
10        for (int j = 0; j < levelCount; j++) {
11            TreeNode node = queue.poll();//出队
12            //如果当前node节点的左右子树都为空，直接返回level即可
13            if (node.left == null && node.right == null)
14                return level;
15            if (node.left != null)
16                queue.add(node.left);
17            if (node.right != null)
18                queue.add(node.right);
19        }
20    }
21    return -1;
22}

 1public int minDepth(TreeNode root) {
 2    if (root == null)
 3        return 0;
 4    //左子树的最小深度
 5    int left = minDepth(root.left);
 6    //右子树的最小深度
 7    int right = minDepth(root.right);
 8    //如果left和right都为0，我们返回1即可，
 9    //如果left和right只有一个为0，说明他只有一个子结点，我们只需要返回它另一个子节点的最小深度+1即可。
10    //如果left和right都不为0，说明他有两个子节点，我们只需要返回最小深度的+1即可。
11    return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
12}

 1public static int minDepth(TreeNode root) {
 2    if (root == null)
 3        return 0;
 4    //如果左子树等于空，我们返回右子树的最小高度+1
 5    if (root.left == null)
 6        return minDepth(root.right) + 1;
 7    //如果右子树等于空，我们返回左子树的最小高度+1
 8    if (root.right == null)
 9        return minDepth(root.left) + 1;
10    //如果左右子树都不为空，我们返回左右子树深度最小的那个+1
11    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
12}