二叉树的最小深度【递归/深度优先搜索】

给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

3<br />   / \<br />  9  20<br />    /  \<br />   15   7<br />返回它的最小深度  2.

分析：很显然，这类题目都是采用基于递归的深度优先搜索算法解决。
思路：
1、如果当前节点不存在左子节点，则以此右子树的根节点计算其最小深度；
2、如果当前节点不存在右子节点，则以此左子树的根节点计算其最小深度；
3、如果当前节点存在左子节点，也存在右子节点，则返回左右子树中的最小深度；
4、如果当前节点为空，则直接返回0.

/**
 * 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)
            return 0;
        if (!root->left)
            return minDepth(root->right) + 1;
           if (!root->right)
            return minDepth(root->left) + 1;
           return min(minDepth(root->left), minDepth(root->right)) + 1;
    }
};

掌握算法思想，不要急于敲下代码，先把问题想清楚。``