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.
这题采用递归很简单，但是要注意函数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;
}
