题目
给定一个整数 n，生成所有由 1 ... n 为节点所组成的** 二叉搜索树 **。
示例：
<pre style="box-sizing: border-box; font-size: 13px; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: rgba(var(--grey-9-rgb),0.04); padding: 10px 15px; color: rgba(var(--grey-9-rgb),1); line-height: 1.6; border-radius: 3px; white-space: pre-wrap;">输入：3
输出：
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释：
以上的输出对应以下 5 种不同结构的二叉搜索树：
1 3 3 2 1
\ / / / \
3 2 1 1 3 2
/ / \
2 1 2 3
</pre>
提示：
0 <= n <= 8
思路1
以每一个i都作一次根节点，i将数列分为两部分，（1，i-1）和（i+1, n)，在前一个区间中让每个j都做一次根节点构成的树作为i的左子树，在后一个区间中让每个k都做一次根节点构成的树作为i的右子树，将所有的情况组合起来
来回只用到一个函数用来生成以i为根节点的树，递归调用即可，结束的条件是left > right，返回[None]
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
if not n:
return []
def new_tree(start, end):
if start > end:
return [None]
all_tree = []
for i in range(start, end+1):
left_tree = new_tree(start, i-1)
right_tree = new_tree(i+1, end)
for left in left_tree:
for right in right_tree:
tree = TreeNode(i)
tree.left = left
tree.right = right
all_tree.append(tree)
return all_tree
return new_tree(1, n)
