leetcode111. 二叉树的最小深度

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-depth-of-binary-tree

题目描述

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

示例1:

输入：root = [3,9,20,null,null,15,7]
输出：2

示例2:
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：
树中节点数的范围在 [0, 105] 内
-1000 <= Node.val <= 1000

DFS 深度优先遍历

解题思路

深度优先遍历时,和计算最大深度不同的是,最大深度只要拿到左右子树的最大深度,加上root 节点就行了,最小值就有一类特殊情况需要考虑了,我用图来演示:

| 在这里插入图片描述
从根节点看,没有右树.这种情况下最小深度就是左树的深度4,因此代码里要对,没有左树和没有右树的情况做下判断.

代码演示

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        return process(root);
    }
	/**
	* dfs 深度优先遍历
	*/
    public int process(TreeNode root){
    	//base case 
        if(root == null){
            return 0;
        }
        //没有左右节点时,返回1,高度就是节点本身
        if(root.left == null && root.right == null){
            return 1;
        }
        int left = process(root.left);
        int right = process(root.right);
        //没有左树的情况
        if(left == 0 && right != 0){
            return right + 1;
        }
        //没有右树的情况
         if(left != 0 && right == 0){
            return left + 1;
        }
        //左树右树都有的情况下,返回最小深度加1
        return Math.min(left,right) + 1;
    }
}

BFS 广度优先遍历

解题思路

在这个题里使用BFS 比 DFS 的优势就在于最小深度,我们不需要遍历所有节点,计算出左右子树的深度,我们只要到最小深度结束时,停止就可以知道最小的深度了,时间复杂度会低很多.
如何判断合适停止呢,一个节点的左右节点都为null 时,就是结束了此时就可以返回最小深度了.

代码演示

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        return bfs(root);
    }
	/**
	* BFS 
	*/
    public int bfs(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        //根节点加进去
        queue.offer(root);
        //跟节点本身的高度是1,所有深度初始化1 
        int depth = 1;
        //开始遍历
        while(!queue.isEmpty()){
        	//每层的宽度
            int N = queue.size();
            //把一层遍历完
            for(int i = 0; i < N ;i++){
                TreeNode cur = queue.poll();
                //如果左右节点都是null 代表这个节点结束了,第一个结束的就是最小深度,直接返回
                if(cur.left == null && cur.right == null){
                    return depth;
                }
                //左右节点加进去
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                 if(cur.right != null){
                    queue.offer(cur.right);
                }
            }
            //遍历完一层深度加1
            depth++;
        }
        return depth;
    }
}