【递归】9. leetcode 104 二叉树的最大深度
1 题目描述
题目链接：二叉树的最大深度
2 解答思路
递归分为三步，接下来就按照这三步来思考问题
第一步：挖掘出相同的子问题 （关系到具体函数头的设计）
第二步：只关心具体子问题做了什么 （关系到具体函数体怎么写，是一个宏观的过程）
第三步：找到递归的出口，防止死递归 （关系到如何跳出递归）
2.1 相同的子问题（函数头设计）
相同的子问题：二叉树的最大深度：这棵树的左子树的深度和右子树的深度中的最大值 + 1
根据这句话，判断出函数头只需要传递一个参数，就是TreeNode* root
下面是leetcode的函数头：
int maxDepth(TreeNode* root) {
}
传入一个TreeNode* root的参数，返回二叉树的最大深度。
因此，我们可以直接使用leetcode给的函数头，不需要再自己创建。
2.2 具体的子问题做了什么（函数体的实现）
具体的子问题：找左子树的深度和右子树的深度的最大值 + 1
这里为什么要+1?
因为递归调用找到的子树的最大深度其实没有算上自己。因为只算上了子树的最大深度，所以要+1，算上自己的深度再返回。
递归的出口?
当节点为空的时候
代码实现：
int maxDepth(TreeNode* root) {
if (root == nullptr)
return 0;
//二叉树的最大深度：这棵树的左子树的深度和右子树的深度中的最大值 + 1
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
