Minimum Depth of Binary Tree

Minimum Depth of Binary Tree.png

解題思路 ：

題目定義如果一邊沒有 child 則不能算為一條 path 所以除了找 min(left, right) 以外另外要再定義兩個條件 如果左邊有 child 右邊沒有 就只檢查左邊的最小高度 反之則檢查右邊的最小高度

C++ code :

<pre><code>
/**

• Definition of TreeNode:
• class TreeNode {
• public:

• int val;
  

• TreeNode *left, *right;
  

• TreeNode(int val) {
  

•     this->val = val;
  

•     this->left = this->right = NULL;
  

• }
  

• }
  */
  class Solution {

public:

/**
 * @param root: The root of binary tree.
 * @return: An integer
 */

int minDepth(TreeNode *root) {
    // write your code here
    if(!root) return 0;
    if(root->left == nullptr && root->right == nullptr) return 1;
    if(root->left && !root->right) return 1 + minDepth(root->left);
    if(root->right && !root->left) return 1 + minDepth(root->right);
    return 1 + min(minDepth(root->left), minDepth(root->right));
}

};