将大问题转化为小问题，通过递归依次解决各个小问题
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组
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)