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.

這題采用遞歸很簡單，但是要注意函數(shù)minDepth()最后的return，要像如下這樣寫

int lDepth = minDepth(root->left);
int rDepth = minDepth(root->right);
return min(lDepth, rDepth)+1;

不能寫為

return min(minDepth(root->left), minDepth(root->right))+1;

否則會導致time exceeded，因為min(A,B)會進行宏替換，導致minDepth(root->left)和minDepth(root->right)都被算了2遍

C代碼

#include <stdlib.h>
#include <assert.h>

#define min(A,B) ((A)<(B)?(A):(B))

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int minDepth(struct TreeNode* root) {
    if(root == NULL)
        return 0;
    if(root->left == NULL)
        return minDepth(root->right)+1;
    if(root->right == NULL)
        return minDepth(root->left)+1;

    int lDepth = minDepth(root->left);
    int rDepth = minDepth(root->right);
    return min(lDepth, rDepth)+1;
}

int main() {
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode*));
    root->val = 1;
    struct TreeNode* left = (struct TreeNode*)malloc(sizeof(struct TreeNode*));
    left->val = 2;
    root->left = left;
    root->right = NULL;
    left->left = NULL;
    left->right = NULL;

    assert(minDepth(root) == 2);

    return 0;
}