111. 二叉树的最小深度

🟢   🔖  树 深度优先搜索 广度优先搜索 二叉树  🔗 力扣 LeetCode

题目

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example 1:

Input: root = [3,9,20,null,null,15,7]

Output: 2

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]

Output: 5

Constraints:

• The number of nodes in the tree is in the range [0, 10^5].
• -1000 <= Node.val <= 1000

题目大意

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

解题思路

思路一：递归

递归求出根节点到叶子节点的深度，输出最小值即可。

---

思路二：BFS

BFS 算法解决的问题的本质，就是在一幅「图」中找到从起点 start 到终点 target 的最近距离。

套用到本题，起点就是 root 根节点，终点就是最靠近根节点的那个叶子节点。

要使用 队列 这种数据结构，层序遍历二叉树，每次将一个节点的所有子节点加入队列，如果某个节点没有子节点，则该节点就是最靠近根节点的那个叶子节点。

注意 while 循环和 for 循环的配合，while 循环控制一层一层往下走，for 循环利用 len 变量控制从左到右遍历每一层二叉树节点。

代码

递归

/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function (root) {
	if (!root) return 0;
	if (!root.left) {
		return minDepth(root.right) + 1;
	}
	if (!root.right) {
		return minDepth(root.left) + 1;
	}
	return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
};

BFS

var minDepth = function (root) {
	if (!root) return 0;
	let queue = [root];
	let depth = 1;
	while (queue.length) {
		let len = queue.length;
		for (let i = 0; i < len; i++) {
			if (!queue[i].left && !queue[i].right) {
				return depth;
			}
			if (queue[i].left) {
				queue.push(queue[i].left);
			}
			if (queue[i].right) {
				queue.push(queue[i].right);
			}
		}
		queue = queue.slice(len);
		depth++;
	}
	return depth;
};

相关题目

题号	标题	题解	标签	难度
102	二叉树的层序遍历	[✓]	树 广度优先搜索 二叉树
104	二叉树的最大深度	[✓]	树 深度优先搜索 广度优先搜索 1+