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. **二. 题目分析** 这道题属于二叉树的深度优先搜索，然后返回深度最小的值，可以递归（当然，也可以使用迭代）来实现。递归退出的条件是到达叶子节点或者到达空子树，使用空子树作为退出条件比较容易进行判断，只要该结点的指针值为`NULL`时，就可以判断空子树的深度为0。因此，可以将每个结点的左右两个子树的深度返回给父节点，父节点选择比较小的深度，然后再返回给祖先结点，以此类推，最后返回给根结点，得到最终结果。 这种方法的时间复杂度为：`O(n)`，空间复杂度为：`O(logn)`。 **三. 示例代码** ~~~ 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) return 0; int Result = 1; int Left = minDepth(root->left); int Right = minDepth(root->right); if (Left * Right) Result += Left > Right? Right : Left; else result += Right + Left; return Result; } }; ~~~ **四. 小结** 这是一道对二叉树进行递归来得到结果的题，递归在二叉树的相关题目中还是考察得比较多的。