题目描述

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

示例:

给定二叉树 [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;
    }
}
pwrliang Algorithms, BFS, DFS, Tree ,

Leave a Reply

Your email address will not be published. Required fields are marked *