数据结构与算法之二叉树: Leetcode 111. 二叉树的最小深度 (Typescript版)

这篇具有很好参考价值的文章主要介绍了数据结构与算法之二叉树: Leetcode 111. 二叉树的最小深度 (Typescript版)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

二叉树的最小深度

https://leetcode.cn/problems/minimum-depth-of-binary-tree/

描述

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

示例 1

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示

树中节点数的范围在 [0, $10^5$ ] 内
-1000 <= Node.val <= 1000

算法实现

1 ）方案 1

/**
 * 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
};