LeetCode 111：二叉樹最小深度（遞歸優化邏輯）

題目描述

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

關鍵陷阱

若節點只有一個子節點，最小深度不是 1，而是需沿著非空子節點繼續遞歸。即：若左子樹為空，最小深度為右子樹最小深度 + 1，反之亦然。只有左右子樹都非空時才取兩者最小值 + 1。

最終遞歸代碼 (C++)

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        if (!root->left && !root->right) return 1;
        if (!root->left) return 1 + minDepth(root->right);
        if (!root->right) return 1 + minDepth(root->left);
        return 1 + min(minDepth(root->left), minDepth(root->right));
    }
};

複雜度

• 時間：O(n)，最壞訪問所有節點。
• 空間：O(h)，遞歸棧深度，h 為樹高。