111. 二叉樹的最小深度

思路

• 假如根結點不存在，高度為 0。
• 假如左右節點不存在，高度為 1。
• 會參考到的是不為空的葉節點到跟節點的高度。
  因此先確認左節點存在，再去看高度；確認右節點存在，再去看高度。
  最後取最小值加上 1（自己這一層）

程式碼

遞迴

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

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$棧空間$O(\log{n})$