圖解LeetCode(入門篇): 111. Minimum Depth of Binary Tree

16th鐵人賽

zaleyu

2024-09-02 05:46:47

219 瀏覽

分享至

111. Minimum Depth of Binary Tree

题目描述：

給定一個二元樹的根節點 root，找出其最小深度。最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。

葉子節點 是指沒有子節點的節點。

Example:

Input: root = [1,2,3,null,null,6,7]
Output: 2

解題思路:
這道題目是關於二元樹的實作題，有兩種常見的解法：遞迴法和迭代法。我們先介紹比較直觀的遞迴法來解決這個問題。

遞迴法的思路是通過遞歸地計算左子樹和右子樹的最小深度來找出二元樹的最小深度。具體步驟如下：

檢查根節點是否為空：如果根節點為空，表示這棵樹沒有節點，直接返回深度為 0。
處理子樹的情況：
- 如果某一側子樹為空，則返回另一側子樹的最小深度加 1，因為此時最小深度只能來自非空的一側。
- 如果兩側子樹都為空（表示當前節點是葉子節點），則按照前面的邏輯，會進入一側子樹為空的判斷，返回另一側的最小深度（即 0）加 1。
- 如果兩側子樹都不為空，則比較兩者的最小深度，返回其中較小的深度加 1。

這樣的遞迴方法可以確保我們找到從根節點到最近葉子節點的最短路徑，從而計算出樹的最小深度。

var minDepth = function(root) {
    if (!root) return 0;

    // If the left subtree is null, recursively find the min depth of the right subtree
    if (!root.left) return minDepth(root.right) + 1;

    // If the right subtree is null, recursively find the min depth of the left subtree
    if (!root.right) return minDepth(root.left) + 1;

    // If both subtrees are not null, return the minimum depth of the two subtrees plus one
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
};

時間複雜度：O(n)，其中 n 是二元樹中的節點數。每個節點都會被訪問一次。
空間複雜度：O(h)，其中 h 是二元樹的高度。遞迴call stack的深度取決於樹的高度。

迭代法的思路是通過廣度優先搜索（BFS）來找出二元樹的最小深度。具體方法是從根節點開始逐層遍歷，每層遍歷時都將當前層的節點放入 queue 中。當遇到第一個葉子節點時，即沒有左或右子節點的節點，返回該葉子節點所在的深度。

由於廣度優先搜索採用的是先進先出（FIFO）的方式來處理節點，因此使用 queue 來實作是最佳選擇。在 queue 中，每次取出節點時，都會將該節點的左右子節點（如果有）加入 queue，直到找到第一個葉子節點為止。這樣的方法可以確保我們在最短路徑上找到最近的葉子節點，從而得出最小深度。

var minDepth = function(root) {
    if (root === null) return 0;

    let queue = [{ node: root, depth: 1 }];

    while (queue.length > 0) {
        let { node, depth } = queue.shift();

        if (node.left === null && node.right === null) {
            return depth;
        }

        if (node.left !== null) {
            queue.push({ node: node.left, depth: depth + 1 });
        }

        if (node.right !== null) {
            queue.push({ node: node.right, depth: depth + 1 });
        }
    }

    return 0;
};