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:
![](https://assets.leetcode.com/uploads/2020/10/12/ex_depth.jpg)
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;
};