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;}//左树右树都有的情况下,返回最小深度加1return 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);}}//遍历完一层深度加1depth++;}return depth;}
}