递归

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

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

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

二叉树的最大深度

二叉树最大深度

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

代码如下:

# 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=1时，需要一种，n=2时，需要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]

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

递归乘法

2020/8/15

递归乘法

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

Notes:

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

递归代码如下:

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:

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

递归代码如下:

# 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