原题
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度 2.
解法
思想
BFS肯定是比DFS快的（最好情况），DFS需要搜索所有节点，BFS只要搜到哪一层有叶子节点就行了（虽然时间复杂度是一个量级的）
代码
class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
queue.offer(null);
int depth = 1;
while(true){
TreeNode node = queue.poll();
if(node == null){
if(queue.isEmpty()) return depth;
else {
depth++;
queue.offer(null);
}
continue;
}
if(node.left == null && node.right == null) return depth;
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null) {
queue.offer(node.right);
}
}
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode111-%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e6%9c%80%e5%b0%8f%e6%b7%b1%e5%ba%a6/
相关推荐
-
leetcode110-平衡二叉树
原题 给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [...
-
leetcode7-整数反转
原题 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。 示例1: 输入： 123 输出： 321 示例2: 输入： -123 输出： -321 示例3: 输...
-
蓝桥杯试题-大小写转换
原题 资源限制 时间限制：1.0s 内存限制：256.0MB 问题描述 输入一个字符串，将大写字符变成小写、小写变成大写，然后输出 输入格式 acbAB 输出格式 ACBab ...
-
leetcode209-长度最小的子数组
原题 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。 示例: 输入: s = ...
-
leetcode173-二叉搜索树迭代器
原题 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。 示例： BSTIterator iterator...
-
leetcode123-买卖股票的最佳时机III
原题 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易（你...
-
剑指offer64-求1+2+…+n
原题（来源Leetcode） 求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。 示例1...
-
leetcode125-验证回文串
原题 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 说明： 本题中，我们将空字符串定义为有效的回文串。 示例 1: 输入: "A man, a ...
-
leetcode154-寻找旋转排序数组中的最小值II
原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。...
-
蓝桥杯试题-哈夫曼树
原题 Description Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。 给出一列数{pi}={p0, p1, …, pn-1}，用这列...
