二叉树的最小深度
- https://leetcode.cn/problems/minimum-depth-of-binary-tree/
描述
-
就 给定一个二叉树,找出其最小深度。
-
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
-
说明:叶子节点是指没有子节点的节点。
示例 1
3
/ \
9 20
/ \
15 7
输入:root = [3,9,20,null,null,15,7]
输出:2
示例 2
输入:root = [2,null,3,null,4,null,5,null,6]
输出:5
提示
- 树中节点数的范围在 [0, 1 0 5 10^5 105] 内
- -1000 <= Node.val <= 1000
算法实现
1 )方案 1文章来源:https://www.toymoban.com/news/detail-457017.html
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function minDepth(root: TreeNode | null): number {
if(!root) return 0;
const q: [TreeNode | null, number][] = [[root, 1]]; // 队列传递根节点 和 层级
while(q.length) {
const [n, l] = q.shift(); // 取出队首元素和层级
// console.log(n); // 访问队首元素
// 如果遇到了叶子节点,直接返回层级
if(!n.left && !n.right) {
return l;
}
n.left && q.push([n.left, l+1]);
n.right && q.push([n.right,l+1]);
}
}
- 思路
- 求最小深度,考虑使用广度优先遍历
- 在广度优先遍历中,遇到叶子节点,停止遍历,返回叶子节点层级即可
- 这个算法,效率很高
- 步骤
- 广度优先遍历整棵树,并记录每个节点的层级
- 遇到叶子节点,返回节点层级,并停止遍历
2 )方案 2文章来源地址https://www.toymoban.com/news/detail-457017.html
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function minDepth(root: TreeNode | null): number {
const queue:TreeNode[] = []
let depth: number = 0 // 最小深度
if(root) {
queue.push(root)
}
while(queue.length) {
// 获取一层的节点数量
let size = queue.length
depth ++
// 获取一层的所有节点 size--
while(size--) {
const first = queue.shift() // 队首出
// 同一层左侧入队
first.left && queue.push(first.left);
// 同一层右侧入队
first.right && queue.push(first.right);
// 到叶子节点即可返回
if(!first.left && !first.right)
return depth
}
}
return depth
}
- 这是官方提供的示例,为何用广度优先遍历?
- 是因为最快,不需要遍历到所有的叶子节点,只需要遍历到最小深度
- 最小深度的定义是:只要再没有孩子节点,则其就是叶子
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function minDepth(root: TreeNode | null): number {
// 无节点情形
if (!root) return 0;
// 没有孩子节点场景
if (!root.left && !root.right) return 1
// 初始化最小值
let min_depth = Number.MAX_SAFE_INTEGER;
// 对左子树进行遍历
root.left && (min_depth = Math.min(minDepth(root.left), min_depth));
// 对右子树进行遍历
root.right && (min_depth = Math.min(minDepth(root.right), min_depth));
// 当前最小值 + 1 并返回
return min_depth + 1
};
- 这个其实也是官方示例,只不过官方是python版本,我改成的TS版本
- 这里用的是递归,也就是深度优先遍历来处理的,所有叶子节点全部遍历
- 在这个过程中求最小值,这个版本没有广度优先遍历算法合适
- 所以,此方案不推荐
到了这里,关于数据结构与算法之二叉树: Leetcode 111. 二叉树的最小深度 (Typescript版)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!