111. Minimum Depth of Binary Tree

1.問題

• 找出最小高度

2.想法

• 提問確認題意:

  • binary tree的類型

• function header, parameter

• test input

• 觀察

• 說明想法

  • 如果不判斷left, right, 就將node丟下去迭代, 這樣會出現一些side effect

  • 比較好的做法是判斷

    • left, right皆不存在時, sum == root->val?

    • left存在時才繼續迭代

    • right存在時才繼續迭代

    • 皆否則return false

• 測試計算複雜度

3.程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) {
            return 0;
        }
        
        if (root->left && !root->right){
            return minDepth(root->left) + 1;
        } else if (root->right && !root->left){
            return minDepth(root->right) + 1;
        }
        
        return min(minDepth(root->left), minDepth(root->right)) + 1;
    }
};