Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        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));   
    }
};

if(!root->left)  return 1 + minDepth(root->right);
if(!root->right)    return 1 + minDepth(root->left);

解释这两句

          root
          /  
         1    
        / \
       2   3
      / 
     4

当根节点的右子树为空的时候，并没有达到叶子节点，因此
1 + minDepth(root->left)
此处注意叶子节点的定义:左右子树均为NULL.