二叉树的最小深度

问题描述：

给定一个二叉树，找出其最小深度。

二叉树的最小深度为根节点到最近叶子节点的距离。

样例

给出一棵如下的二叉树:

        1

     /     \ 

   2       3

          /    \

        4      5  

这个二叉树的最小深度为 2

解题思路：

当二叉树为空时，返回0；当左子树为空时，返回右子树的深度；当右子树为空时，返回左子树的深度；当左右子树都不为空时，返回最小的值。

代码实现：

/**  * 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==NULL) return 0;         int lcount=minDepth(root->left);         int rcount=minDepth(root->right);         if(root->left==NULL) return rcount+1;         if(root->right==NULL) return lcount+1;         if(lcount+1>rcount+1) return rcount+1;         else return lcount+1;     } };

解题感悟：

一开始没有想太多，就以为用递归将左子树和右子树分开算最后返回小的那个就好了，忽略了斜树的情况，这是返回值一直是1。考虑斜树的情况，当左子树为空时，返回右子树的深度；当右子树为空时，返回左子树的深度。