Day90 | 灵神 | 二叉树 做题方法 二叉树的最大深度

灵神的做题方法

首先

类似于高中的整体法，将左右子树分别看为一个整体

其次

再次

最后

边界条件和非边界条件怎么算也得想清楚

并且在写代码之前还要想清楚为什么这样做是对的，可以用数学归纳法来说明

边界条件就类似于图中的1，而非边界条件就类似于图中的2

笔者觉得挺好的做题方法

1.先想明白递归函数的含义，比如在下面的题中就是求以传入参数t为根节点的树的最大深度

2.想明白递归函数参数和返回值

3.想清楚递归函数结束条件，对应上面的边界条件

4.想清楚递归函数本层逻辑，对应上面的非边界条件

104.二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode）

思路：

1.递归函数意义

求以传入参数t为根节点的树的最大深度

2.参数和返回值

int get_depth(TreeNode *t)

返回值就是以t为根结点的树的最大深度

3.终止条件（边界条件）

如果我们碰到了空节点，那么它的深度肯定就是0了

if(t==nullptr)
	return 0;

4.本层逻辑（非边界条件）

求左子树最大值和右子树最大值，返回两者最大值+1就是答案

int left=get_depth(t->left);
int right=get_depth(t->right);
return max(left,right)+1;

完整代码：

class Solution {
public:
    int get_depth(TreeNode *t)
    {
        if(t==nullptr)
            return 0;
        int left=get_depth(t->left);
        int right=get_depth(t->right);
        return max(left,right)+1;
    }
    int maxDepth(TreeNode* root) {
        return get_depth(root);
    }
};