LeetCode算法题-Minimum Depth of Binary Tree(Java实现)

LeetCode算法题-Minimum Depth of Binary Tree(Java实现)

这是悦乐书的第168次更新,第170篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第27题(顺位题号是111)。给定二叉树,找到它的最小深度。最小深度是沿从根节点到最近的叶节点的最短路径上的节点数。叶子节点是没有子节点的节点。例如:

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

       3
      /  \
     9   20
        /  \
       15   7

返回其最小深度= 2。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

之前我们有解过最大深度的题,今天这道题相反,求最短路径,那是不是直接将原来代码中的最大改为最小即可?如果你这样试过,会发现根本不是那么回事!

特殊情况一:当传入的二叉树为空时,最短路径就是0。

特殊情况二:当传入的二叉树只有根节点时,最短路径是1.

正常情况:当某一节点的左子节点为空时,这时我们需要求其右子节点的最短路径;当某一节点的右子节点为空时,这时我们需要求其左子节点的最短路径;当某一节点的左子节点和右子节点都不为空时,这时我们要求其左子树和右子树的最短路径。

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    if ((root.left == null) && (root.right == null)) {
        return 1;
    }
    if (root.left == null) {
        return minDepth(root.right) + 1;
    }
    if (root.right == null) {
        return minDepth(root.left) + 1;
    }
    return 1+Math.min(minDepth(root.left), minDepth(root.right));
}


03 第二种解法

除了上面的递归外,我们依旧可以使用遍历的方法。此解法与求最大深度时的第三种解法类似,也是利用队列,只是多了一步判断:当左右节点都为空时,此节点是叶子节点,需要更新最短路径的值。

public int minDepth2(TreeNode root) {
    if (root == null) {
        return 0;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int minDepth = Integer.MAX_VALUE;
    int depth = 1;
    while (!queue.isEmpty()) {
        int size = queue.size(); 
        while (size > 0) {
            TreeNode t = queue.poll();
            if (t.left != null) {
                queue.offer(t.left);
            }
            if (t.right != null) {
                queue.offer(t.right);
            }
            if (t.left == null && t.right == null) {
                minDepth = Math.min(minDepth, depth); 
            }
            size--;
        }
        depth++;
    }
    return minDepth;
}


04 小结

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!