递归实现二叉树的最小深度（C++）

111. 二叉树的最小深度

思路：二叉树的最小深度与最大深度的实现有一些区别，要注意是叶子节点到根节点的路径长度最小的为二叉树的最小深度，所以要注意一个节点只有一个子节点的情况。

1. 确定返回类型和参数列表：返回类型为int类型，参数为TreeNode*类型；
2. 确定终止条件：当前节点为空时，返回0；
3. 确定单层递归逻辑：如果当前节点的左子树不为空，右子树为空，则返回左子树的最小深度；如果当前节点的右子树不为空，左子树为空，则返回右子树的最大深度；如果左子树不为空，右子树也不为空，则将两者深度最小的一个加1，然后返回该值，即返回当前子树的最小深度。

代码：

class Solution {	//111. 二叉树的最小深度  递归
public:
	int minDepth(TreeNode* root) {
		if (root == nullptr) return 0;
		if (root->left != nullptr && root->right == nullptr) {
			return minDepth(root->left) + 1;
		}
		if (root->left == nullptr && root->right != nullptr) {
			return minDepth(root->right) + 1;
		}
		return min(minDepth(root->left), minDepth(root->right)) + 1;
	}
};

参考资料：代码随想录