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;//二叉树的最大深度:这棵树的左子树的深度和右子树的深度中的最大值 + 1return max(maxDepth(root->left), maxDepth(root->right)) + 1;}