递归思路讲解

淩亂°似流年 2023-09-27 18:05 66阅读 0赞

最近刷到了树这一模块的算法题，树相关的算法题几乎都是用递归来实现的，但递归的思路却有点抽象，每次遇到递归，都是通过递归来深度或广度地遍历树，但对于递归遍历树的遍历路线，却有点抽象难懂，不知道遍历的路线是怎么样的，也对于返回的路线有点懵懂。

虽然知道是用递归，也知道递归可以一层一层从上到下地遍历，大体上的一个遍历路线是明白的，但是真要将递归一层层拆解分析的话，我还是有点不知所措的，所以今天研究了一小时，彻底将递归的一层层遍历拆解分析透彻了。

记录一下拆解分析的过程，以防之后又忘了，方便回顾。

![df33d62489cc4669a5cb8d22522068c9.png][]

拿上面这棵树来分析，遍历的代码是：

private void dfs(TreeNode root, int depth) {
            if (root == null) {
                return;
            }
            // 先访问 当前节点，再递归地访问 右子树 和 左子树。
            if (depth == res.size()) {   // 如果当前节点所在深度还没有出现在res里，说明在该深度下当前节点是第一个被访问的节点，因此将当前节点加入res中。
                res.add(root.val);
            }
            depth++;
            dfs(root.right, depth);
            dfs(root.left, depth);
        }

>  **这里将 dfs（root，0）一层层地拆解分析：**
> 
> **1.首先传入树的根节点root，和depth = 0**
> 
> **2.进入方法先判断root 是否为null， 为null 则return，这里也是后面递归的终止条件，当遍历到叶子结点下一节点时返回上一层。**
> 
> **3.进入到dfs（root.right,depth）递归环节，root.right = 1,depth = 0**
> 
> （1）先判断root.right 是否为null，这里不为null，root.right = 3 ，depth = 1
> 
> （2）继续向下递归，先判断root.right.right 是否为null，这里不为null，root.right.right = 6 ，depth = 2
> 
> （3）继续向下递归，先判断root.right.right.right是否为null，这里为null，则return到上一层，跳到root.right.right = 6 ，depth = 2这一层
> 
> （4）在root.right.right = 6 ，depth = 2这一层，dfs（root.right.right.right,depth）已结束，执行下一句dfs（root.right.right.left,depth），进入方法后判断是否为null，不为null，root.right.right.left = 8,depth = 3
> 
> （5）在root.right.right.left = 8,depth = 3这一层，分别递归右子树和左子树，都为null，则返回root.right.right.left = 8,depth = 3这一层；同时root.right.right = 6 ，depth = 2这一层已经全部结束，返回到了root.right = 3 ，depth = 1这一层
> 
> （6）在root.right = 3 ，depth = 1这一层，右子树已经遍历完毕，开始遍历左子树dfs（root.right.right,depth）,左子树为null，则root.right = 3 ，depth = 1这一层的左右子树也已经遍历完毕，所以回到了root.right = 1,depth = 0
> 
> **4.此时dfs（root.right,depth）这句代码已经全部执行完毕，到了dfs（root.left,depth）这句话的执行，root.left = 2,depth = 1,然后像第3步一样开始从右子树--->左子树地递归**
> 
> **思路其实就像是套娃一样，一个大的盒子里装了两个小的套娃，这两个套娃里分别装着一层层的套娃，我们要先结束一个大的套娃，再结束另一个大的套娃。**

> 如果文字看的比较抽象，可以参考这个视频辅助理解：
> 
> [递归算法很难？小s带你10分钟完成手把手推导，用递归求二叉树深度][s_10]

[df33d62489cc4669a5cb8d22522068c9.png]: https://img-blog.csdnimg.cn/df33d62489cc4669a5cb8d22522068c9.png
[s_10]: https://www.bilibili.com/video/BV1g741137Wq/?spm_id_from=333.337.search-card.all.click&vd_source=cd1022f068ce9ec092d3068164329eec