递归

递归是一种自己调用自己的编程方式，递归的一个最大的特点是: 将大型复杂的问题转化为较小的与原始问题类似的问题。递归的代码设计简单明了。
它包含的三个条件是: 1. 边界条件，2. 递归前进段， 3. 递归返回段

设计递归程序一般包含下面两个: 1.设计递归式， 2. 给定终止条件

我们将使用leetcode中的例题进行记录学习

二叉树的最大深度

我们知道二叉树只包含左右孩子两个节点，并且节点的数值可以为空，那么一个根节点开始的二叉树，去掉根节点后可以看作两个二叉树，依次类推，那么最后一个节点处可以看作左右孩子节点是空的。因此递归终止条件是节点是否为空，如果为空，返回0(说明这是最后子节点，深度为0)，否则进入设计递归式，由于存在左右两个节点的方向，因此最大深度就是 $max(l_{tree}, r_{tree})$ ,既然在此处节点可以向两边走去说明递归返回段是 $max(l_{tree}, r_{tree}) + 1$ ，在前进段中，分别向左子节点和右子节点进行搜索。因此

代码如下:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:

        if root is None:
            return 0
        else:
            l_tree = self.maxDepth(root.left)
            r_tree = self.maxDepth(root.right)
            return max(l_tree, r_tree) + 1

爬楼梯问题

爬楼梯问题也是典型的递归解决的问题，通过题目我们反向推断：到达最后一层( $n$ )层，要么是 $n-1$ 层过来的，要么是 $n-2$ 层过来的，那么对于 $n-1$ 层来说也是同理于 $n$ 层。因此可以使用递归进行计算。递归边界条件就是当n=1时，需要一种，n=2时，需要2种走法，递归的前进条件就是不断递归式求解 $f(n) = f(n-1) + f(n-2)$

递归代码如下:

class Solution:
    def n_stairs(self, n):

        if n == 1:
            return 1
        elif n == 2:
            return 2
        
        return self.n_stairs(n-1) + self.n_stairs(n-2)
    def climbStairs(self, n: int) -> int:
        
        if n == 1:
            return 1
        if n == 2:
            return 2

        return self.n_stairs(n-1) + self.n_stairs(n-2)

但是一个最大问题是:这里的递归求解会占用较大内存和时间，因此改写成循环方式实现。

迭代代码如下:

class Solution:

    def climbStairs(self, n: int) -> int:
        
        if n == 1:
            return 1
        temp_list = [0] * n
        temp_list[0] = 1
        temp_list[1] = 2

        for i in range(2,n):
            temp_list[i] = temp_list[i-1] + temp_list[i-2]
        return temp_list[n-1]

这个过程中不断地保存每次结果，直到到达求解的第 $n$ 个数据。

递归乘法

2020/8/15

递归乘法

题目: 输入两个数 $A$ 和 $B$ ，在不使用 $*$ 的情况下，计算它们的乘积，可以使用加、减、移位运算。问题描述的很清楚，比如输入 $A=3$ , $B=4$ 时，除了使用 $3*4=12$ 外，我们最能想到的做法是 $4+4+4=12$ 。这里使用递归的思路很容易理解， $n$ 个4相加的过程，本质上就是每一步+4。这样就能够获得一个式子 $multiply(A, B) = multiply(A-1, B) + B$ 。接下来我们看看递归边界，当 $A=0$ 时，乘积为0，自然返回0。当 $A=1$ 时，那么返回B。

Notes:

这里最重要的一点是， $A$ 一定要是 $A$ 和 $B$ 两个数中最小的那个，不然不断地递归操作会使得内存耗尽。

递归代码如下:

class Solution:
    def multiply(self, A: int, B: int) -> int:
        
        ## 注意将加次项设置为最小的，这个执行的递归的深度
        if A > B:
            A, B = B, A
        if A == 0:
            return 0
        elif A == 1:
            return B
        
        return self.multiply(A-1, B) + B

二叉树的中序遍历

2020/8/15

二叉树的中序遍历

给定一个二叉树，返回其中序遍历。

二叉树的中序遍历: 考察到一个节点后，将其暂存，遍历完左子树后，再输出该节点的值，然后遍历右子树。根据概念，我们使用递归，并且这个过程中存储对应的values数值。

Notes:

注意的一点是，由于达到叶子节点，没有返回的内容，因此要使用全局的 $list$ 保存对应节点的数据，这样的话，必须借助一个 $helper$ 函数。

递归代码如下:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


### 二叉树的中序遍历: 考察到一个节点后，将其暂存，遍历完左子树后，再输出该节点的值，然后遍历右子树

class Solution:

    def helper(self, root, a_list):
        if root is  not None:
            self.helper(root.left, a_list)
            a_list.append(root.val)
            self.helper(root.right, a_list)

    def inorderTraversal(self, root: TreeNode) -> List[int]:
        temp_list = []   
        self.helper(root, temp_list)
        return temp_listB

递归讲解及其python实现例题(leetcode)

递归讲解及其python实现例题(leetcode)

递归

二叉树的最大深度

爬楼梯问题

递归乘法

二叉树的中序遍历