111. Minimum Depth of Binary Tree
111. Minimum Depth of Binary Tree
🟢 🔖 树 深度优先搜索 广度优先搜索 二叉树 🔗 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, 105]. -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;
};