LeetCode Minimum Depth of Binary Tree：二叉樹最小深度

題目描述

給定二叉樹，求最小深度：從根節點到最近葉子節點的路徑節點數。

遞歸解法

後序遍歷。空節點深度 0。葉子節點深度 1。非葉子節點：若左右子樹皆存在，取較小深度 +1；若僅一側存在，取該側深度 +1（避免誤將單分支節點視為葉子）。

C++ 實現

struct TreeNode { int val; TreeNode *left, *right; TreeNode(int x):val(x),left(nullptr),right(nullptr){} };
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        int L = minDepth(root->left);
        int R = minDepth(root->right);
        if (L && R) return 1 + min(L, R);
        return 1 + L + R; // 一方為0，取另一方
    }
};

關鍵點

• 空節點深度 0，葉子深度 1。
• 單分支節點不能取 min(0, 深度)=0，必須取非零側深度。
• 時間 O(N)，空間 O(H)。