LintCode (155) 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.

Have you met this question in a real interview? 

Yes

Example

Given a binary tree as follow:

        1

     /     \ 

   2       3

          /    \

        4      5  

The minimum depth is 2

这个题目有个陷阱。。。如果简单用分治的模板，空返0， min(左，右）+1， 就算上当了。。。这个depth算的是node数目，比如,2 # 6 那么这个例子的答案就变为3了。。。所以 不从root=0返回，而是从!root-left && !root->right 返回1

/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: The root of binary tree. * @return: An integer */ int minDepth(TreeNode *root) { // write your code here if (!root) return 0; if (!root->left && !root->right) return 1; int left=INT_MAX; if (root->left) left=minDepth(root->left); int right=INT_MAX; if (root->right) right=minDepth(root->right); return min(left, right)+1; } };