将大问题转化为小问题，通过递归依次解决各个小问题
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组
char[]的形式给出。
classSolution: defreverseString(self, s: List[str]) ->None: """ Do not return anything, modify s in-place instead. """defrev_rec(s, i, j): ifi>=j: returns[i], s[j] =s[j], s[i] rev_rec(s, i+1, j-1) returnrev_rec(s, 0, len(s) -1) return给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
classSolution: defswapPairs(self, head: ListNode) ->ListNode: ifheadisnotNoneandhead.nextisnotNone: head_next_pair=self.swapPairs(head.next.next) p=head.nexthead.next=head_next_pairp.next=headhead=preturnhead给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
注意：此题用来训练递归思维有理论意义，但是实际上算法返回的树并不是 deep copy，多个树之间会共享子树。
classSolution: defgenerateTrees(self, n: int) ->List[TreeNode]: defgenerateTrees_rec(i, j): ifi>j: return [None] result= [] forminrange(i, j+1): left=generateTrees_rec(i, m-1) right=generateTrees_rec(m+1, j) forlinleft: forrinright: result.append(TreeNode(m, l, r)) returnresultreturngenerateTrees_rec(1, n) ifn>0else []斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定 N，计算 F(N)。
classSolution: deffib(self, N: int) ->int: mem= [-1] * (N+2) mem[0], mem[1] =0, 1deffib_rec(n): ifmem[n] ==-1: mem[n] =fib_rec(n-1) +fib_rec(n-2) returnmem[n] returnfib_rec(N)