https://leetcode-cn.com/problems/unique-binary-search-trees-ii/

    注意审题：

    • 这是个二叉搜索树，利用这个性质解题就不难。
    • 需要返回的是树的list，肯定要在某个节点建树。

    利用dfs的时候，想了半天不会存和建树，最后看了答案才恍然大悟，以 i 为root的时候，利用dfs获得所有左子树和右子树。

    递归出口返回什么也很纠结，返回None 和[]都是错的，要返回[None]
    因为你要接一个空节点的时候，这个空节点是list从遍历过来的，所以返回[None]是正确的。

    1. class Solution:
    2.     def generateTrees(self, n: int) -> List[TreeNode]:
    3.         # 审题 二叉**搜索**树
    4.         # 返回的是树的list！
    5.         if not n:return []
    6.         def dfs(start,end):
    7.             if start>end:return [None]
    8.             ans=[]
    9.             for i in range(start,end+1):
    10.                 lefttree=dfs(start,i-1)
    11.                 righttree=dfs(i+1,end)
    12.                 for l in lefttree:
    13.                     for r in righttree:
    14.                         cur=TreeNode(i)
    15.                         cur.left=l
    16.                         cur.right=r
    17.                         ans.append(cur)
    18.             return ans
    19.         return dfs(1,n)