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.

 

to see which companies asked this question

 

刚开始写的代码是这样的。

if(root==NULL) return 0;        return min(mindeep(root->right)+1,mindeep(root->left)+1);

看出问题了吧，这段代码“看上去”是正确的，但是对于这种结构

1             /             2

5             / \            4   8           /     \          11      4 对于以上两种结构都是计算错误，因为第一种结构它把根节点自己也看做一条路径，这样是不对的。 所以要做判断，当根节点只有一条路径的时候，只计算一条路径的长度，而不是继续选最小了。

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    int minDepth(TreeNode* root){        if(root==NULL) return 0;        if(root->left&&root->right) return min(minDepth(root->left)+1,minDepth(root->right)+1);        else if(root->left==NULL||root->right==NULL) return max(minDepth(root->right)+1,minDepth(root->left)+1);    }};