二叉樹的最小深度

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

描述

• 就 給定一個二叉樹，找出其最小深度。

• 最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數(shù)量。

• 說明：葉子節(jié)點是指沒有子節(jié)點的節(jié)點。

示例 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

提示

• 樹中節(jié)點數(shù)的范圍在 [0, $10^5$] 內(nèi)
• -1000 <= Node.val <= 1000

算法實現(xiàn)

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]]; // 隊列傳遞根節(jié)點 和 層級
    while(q.length) {
        const [n, l] = q.shift(); // 取出隊首元素和層級
        // console.log(n); // 訪問隊首元素
        // 如果遇到了葉子節(jié)點，直接返回層級
        if(!n.left && !n.right) {
            return l;
        }
        n.left && q.push([n.left, l+1]);
        n.right && q.push([n.right,l+1]);
    }
}

• 思路
  • 求最小深度，考慮使用廣度優(yōu)先遍歷
  • 在廣度優(yōu)先遍歷中，遇到葉子節(jié)點，停止遍歷，返回葉子節(jié)點層級即可
  • 這個算法，效率很高
• 步驟
  • 廣度優(yōu)先遍歷整棵樹，并記錄每個節(jié)點的層級
  • 遇到葉子節(jié)點，返回節(jié)點層級，并停止遍歷

2 ）方案 2文章來源地址http://www.zghlxwxcb.cn/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) {
        // 獲取一層的節(jié)點數(shù)量
        let size = queue.length
        depth ++
        // 獲取一層的所有節(jié)點 size--
        while(size--) {
            const first = queue.shift() // 隊首出
            // 同一層左側(cè)入隊
            first.left && queue.push(first.left);
            // 同一層右側(cè)入隊
            first.right && queue.push(first.right);
            // 到葉子節(jié)點即可返回
            if(!first.left && !first.right)
                return depth
        }
    }
    return depth
}

• 這是官方提供的示例，為何用廣度優(yōu)先遍歷？
• 是因為最快，不需要遍歷到所有的葉子節(jié)點，只需要遍歷到最小深度
• 最小深度的定義是：只要再沒有孩子節(jié)點，則其就是葉子

/**
 * 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 {
    // 無節(jié)點情形
    if (!root) return 0;
    // 沒有孩子節(jié)點場景
    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));
    // 當(dāng)前最小值 + 1 并返回
    return min_depth + 1
};

• 這個其實也是官方示例，只不過官方是python版本，我改成的TS版本
• 這里用的是遞歸，也就是深度優(yōu)先遍歷來處理的，所有葉子節(jié)點全部遍歷
• 在這個過程中求最小值，這個版本沒有廣度優(yōu)先遍歷算法合適
• 所以，此方案不推薦

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法之二叉樹: Leetcode 111. 二叉樹的最小深度 (Typescript版)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！