首先,先说一句套娃的话,要想解决递归问题,你得先理解递归。
递归,简单理解就是俄罗斯套娃。。
递归虽然很烦人,但是可以便捷的用来解决一些问题,比如二叉树的遍历、斐波拉契数列等等。
之前也一直有点晕乎,后来看了参考【1】的视频,感觉有点开窍了,写下自己的感悟。
解决递归问题的主要步骤:
1. 定义函数(声明函数)
首先自然是要定义函数,但是实际上在定义函数的过程中我们已经用到了这个还没有写完的函数,所以说第一步是声明函数更加准确。
2. 在每一层递归里面函数做什么?
以 二叉树的前序遍历为例,在每一层递归的过程中,我们要做的就是:
- 记录当前结点的值;
- 遍历左子树;
- 遍历右子树;
其中,遍历左/右子树,就需要用到我们这个还没有写完的函数,也就是直接使用正在写的函数即可,这也是递归的精髓。
3. 什么时候结束函数?边界条件?
这一步是最重要的,因为如果没有边界条件,那么递归就是无穷尽的,自然就陷入死循环了,所以必须要知道什么时候出递归。
对于二叉树的遍历来说,如果我们当前的节点为空,自然就结束了。
对于二叉树来说,我们可以想象每个叶子结点下方都有两个空节点,左边一个,右边一个,那么遍历到这一个空结点的时候自然就结束当前这一层函数调用,返回上一层了(对于上一层的结点)。
根据上面的步骤,不难写出二叉树前序遍历的递归解法:
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
re = []
def traversal(root): # 对应第一步
if root==None: # 对应第三步
return
re.append(root.val) # 对应第二步
traversal(root.left) # 对应第二步
traversal(root.right) # 对应第二步
traversal(root) # 不要忘记调用函数
return re
参考
本文由mdnice多平台发布