给定一个有序序列 1 ... n，为了根据序列构建一棵二叉搜索树。我们可以遍历每个数字 i，将该数字作为树根，1 ... (i-1) 序列将成为左子树，(i+1) ... n 序列将成为右子树。于是，我们可以递归地从子序列构建子树。 在上述方法中，由于根各自不同，每棵二叉树都保证是独特的。
可见，问题可以分解成规模较小的子问题。因此，我们可以存储并复用子问题的解，而不是递归的（也重复的）解决这些子问题，这就是动态规划法。
算法
问题是计算不同二叉搜索树的个数。为此，我们可以定义两个函数：
G(n): 长度为n的序列的不同二叉搜索树个数。
F(i,n): 以**i为根**的不同二叉搜索树个数(1 ≤ i ≤ n)。
可见，
G(n)是我们解决问题需要的函数。
稍后我们将看到, G(n) 可以从F(i,n) 得到，而F(i,n) 又会递归的依赖于G(n)。
首先，根据上一节中的思路，不同的二叉搜索树的总数 G(n)，是对遍历所有 i (1 List[TreeNode]:
return self.generateSonTrees(1, n) if n else []
# 构建左右子树
def generateSonTrees(self, start: int, end: int) -> List[TreeNode]:
if start > end:
return [None, ]
ans = []
# 选择每个数字作为根节点
for i in range(start, end+1):
# 左子树
leftTree = self.generateSonTrees(start, i-1)
# 右子树
rightTree = self.generateSonTrees(i+1, end)
for lt in leftTree:
for rt in rightTree:
root = TreeNode(i)
root.left = lt
root.right = rt
ans.append(root)
return ans
2.2.2、动态规划（备忘录）
class Solution:
def __init__(self) -> None:
# 备忘录
self.d = {}
def generateTrees(self, n: int) -> List[TreeNode]:
"""
1. dp问题: dp[i] = dp[i - 1]为左子树 * dp[i+1]为右子树
"""
return self.help(1, n) if n else []
def help(self, i, j):
if (i, j) in self.d:
return self.d[(i, j)]
ans = []
# 根节点
for v in range(i, j + 1):
# 递归找到所有的左子树
for left in self.help(i, v - 1):
# 递归找到所有的右子树
for right in self.help(v + 1, j):
root = TreeNode(v)
root.left, root.right = left, right
ans += [root]
# 将i,j对应的结果存储起来
self.d[(i, j)] = ans or [None]
return self.d[(i, j)]
