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;
否則會導(dǎo)致time exceeded，因為min(A,B)會進(jìn)行宏替換衙四，導(dǎo)致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;
}
