题目

给定一个整数 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)