听不少大佬建议过——力扣刷题要从树开始！
因为可以建立起套路化的思路~ 另外就是锻炼好递归的思想
所以我们从树开始~
本专题采用前面提到的 “兔系刷题法”
不求钻研多种解法只求快速见题型快速刷题！

另外力扣评论区里看见的——
树的题目写不出来，多背几个模版就行。
前中后序、广度深度遍历、路径和、深度，直径，这些全部背下来。
感觉很有道理！多背些多理解些套路嘛！

本期选取了一道我非常耐的题
来细扣一下递归的这些个小套路~
【图片源自b站迷糊老师】hhh
在这里插入图片描述

不废话先来看题

题目中的“自底向上” "自顶向下”在下面会进行一个详解

文章目录

104.二叉树的最大深度
运用递归解决树的问题

2021.6.25 更新 leetcode110 平衡二叉树练一下吧朋友们一模一样的思路

本文食用建议
打开104. 二叉树的最大深度
打开本文
用个30-60min 把这题以及相关方法整明白
啥？时间不够？收藏下慢慢看呗[doge]

另外有什么相关题你做到的时候想到这个小套路了？
评论区见！
（之后我要是遇到可以用这类方法解决的题目会更新进来的~）
在这里插入图片描述

104.二叉树的最大深度

递归
深度优先搜索 DFS

104. 二叉树的最大深度 easy

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

解题思路

【1】自顶向下

21.6.26更新这里注意自顶向下对于同一个节点，
递归函数会被重复调用，导致时间复杂度较高 为O(N)

在这里插入图片描述
具体思路就是

一层一层地进行搜索
每搜索新的一层深度 depth 就 +1
到最底下更新一下 ans

【2】自底向上

21.6.26更新这里注意自底向上注意这个方法是“提前阻断”的
也就是说一旦碰到了不满足平衡二叉树的节点就会进行“剪枝” （子节点剪掉的话父节点同样剪掉）

在这里插入图片描述
这个方法之前写过一篇博客
简单画了一下这个寻找depth值的过程刚好吻合~

发现叶子节点 ------ return 0 + 1
这个 0 + 1 就是父节点的 Ldepth （看下面的代码）

然后再慢慢往上倒就行了~
如果有上一层 ------ return Math.max(1, Rdepth) + 1
再往上同理

递归自顶向下

关键是计算深度方法 public void _maxDepth(TreeNode root, int depth)

class Solution {
    public int ans = 0;
    public void _maxDepth(TreeNode root, int depth) {
        if (root == null) return;
        if (root.left == null && root.right == null){
            ans = Math.max(ans, depth);//到最底下更新一下 ans
        }
        _maxDepth(root.left, depth + 1);//逐层的深入 每进入新的一层 就把深度加一~
        _maxDepth(root.right, depth + 1);//左边深入完 再来深入右边~
    }
    public int maxDepth(TreeNode root){
        _maxDepth(root, 1);
        return ans;
    }
}

在这里插入图片描述

递归自底向上

关键是计算深度方法 public int maxDepth(TreeNode root)

class Solution {
    public int maxDepth(TreeNode root) {
        //自下向上
        if (root == null){
            return 0;
        }
        int Ldepth = maxDepth(root.left);
        int Rdepth = maxDepth(root.right);
        return Math.max(Ldepth, Rdepth) + 1;
        //每次递归给出一个结果 依次是 最底层的子节点返回1 （如果有的话）往上一层返回2 再往上是返回3...   
    } 
}

在这里插入图片描述

利用三元表达式实现一行递归

实质上是自底向上的方法~

class Solution{
    public int maxDepth(TreeNode root){
        return root == null ? 0 : Math.max( maxDepth(root.left), maxDepth(root.right) ) + 1;
    }
}

写了这么多枯燥的代码
总结下方法论

在这里插入图片描述

运用递归解决树的问题

借鉴 LeetBook 中的树专题
的总结

该说不愧是力扣官方的么
总结得相当精辟呐！
（同样采用了leetcode104这个例子~）

1.自顶向下

每个递归层级
访问节点来计算一些值
递归调用函数时将这些值传递到子节点
传递过程中达到一定条件就更新结果

所以可以被认为是一种前序遍历

套路如下：

【0】设置好最终答案设置好递归函数 (输入节点，输入临时答案) 函数用于计算出答案 answer

【1】设置特殊值退出条件

【2】遍历到某个节点时更新答案

【3】遍历左子树 & 遍历右子树

return specific value for null node
update the answer if needed                      // answer <-- params
left_ans = top_down(root.left, left_params)		// left_params <-- root.val, params
right_ans = top_down(root.right, right_params)	// right_params <-- root.val, params
return the answer if needed                      // answer <-- left_ans, right_ans

下面看个例子加深下印象

求二叉树深度的例子

伪代码：

return if root is null
if root is a leaf node:
    answer = max(answer, depth)         // update the answer if needed
maximum_depth(root.left, depth + 1)      // call the function recursively for left child
maximum_depth(root.right, depth + 1)		// call the function recursively for right child

[0]

private int answer = 0;
private void maximum_depth(TreeNode root, int depth)

[1]

if (root == null){
    return;
}

[2]

if (root.left == null && root.right == null){
    answer = max(answer, depth);
}

更新结果的过程~
在这里插入图片描述

[3]

maximum_depth(root.left, depth + 1);//遍历左子树 同时让深度+1
maximum_depth(root.right, depth + 1);

在这里插入图片描述

这之后答案更新为 4

在这里插入图片描述

2.自底向上

每个递归层次上
首先对所有子节点递归地使用调用函数
然后根据返回值和根节点本身的值得到答案

所以这个过程很像是后序遍历
先深入到一个地方再更新结果

解题套路
【0】设置好递归函数（只需要输入节点即可）函数可以直接返回答案

【1】设置特殊值退出条件

【2】对左右子树调用递归函数

【3】左子树返回一个值右子树返回一个值最后将两边的值进行汇总得到最终解

return specific value for null node
left_ans = bottom_up(root.left)			// call function recursively for left child
right_ans = bottom_up(root.right)		// call function recursively for right child
return answers                           // answer <-- left_ans, right_ans, root.val

求二叉树深度的例子

伪代码：

return 0 if root is null                 // return 0 for null node
left_depth = maximum_depth(root.left)
right_depth = maximum_depth(root.right)
return max(left_depth, right_depth) + 1	// return depth of the subtree rooted at root

[0]

public int maximum_depth(TreeNode root)

[1]

if (root == null){
    return 0;
}

[2]

int left_depth = maximum_depth(root.left);
int right_depth = maximum_depth(root.right);

[3]

return Math.max(left_depth, right_depth) + 1;

这里要先求出每一步的左子树的深度再求出每一步右子树的深度最后求二者最大值 + 1

在这里插入图片描述

最终结果
在这里插入图片描述

3.递归秒杀二叉树套路！

遇到树问题判断一下是用 自顶向下 还是 自下向上

首先思考两个问题——

是否可以确定一些参数在每一步节点的遍历中都能更新这些参数最终达到答案
（可以参考上面 $举出的自顶向下求深度的例子$ 就是每一步都让参数depth ++）
是否可以使用这些参数和节点本身的值来决定什么应该是传递给它子节点的参数

如果这两个都可以做到使用自顶向下

自顶向下比较类似前序遍历哦~
自顶而下地让我们的变量进行变化~
求深度题目中的 depth 从根节点开始每到新的一层就加1

如果不行或者没啥头绪？再思考下——

对于树中任意一个节点如果你知道它子节点的答案你能计算出该节点的答案嘛？

（参考上面 $自下向上求深度$ 的例子如果你知道了一个节点左右子树的深度那这个节点的深度自然而然就是 left_ans + right_ans + 1 )

如果肯定的那就使用自底向上

自底向上比较类似后序遍历哦~
自底向上地让我们的变量进行变化~
求深度题目中的 depth 从叶子节点往上进行depth的更新

4.小结

总而言之
选择啥方法？

从根开始一点点往下更新结果
或者先遍历到节点一点点往上更新结果

就这两个方法
哪个方法能做出来题就选择哪个呗？
争取后期能更新更多相关题型触类旁通下~（虽说感觉也没人看小声bb）

文章目录

104.二叉树的最大深度

解题思路

递归 自顶向下

递归 自底向上

利用三元表达式实现一行递归

运用递归解决树的问题

1.自顶向下

求二叉树深度的例子

2.自底向上

求二叉树深度的例子

3.递归秒杀二叉树套路！

4.小结

递归自顶向下

递归自底向上