95. 不同的二叉搜索树 II

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

示例 1：

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

• 1 <= n <= 8

Python 解答：
1.递归

# 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 visit(self, tree):
    #     if not tree:
    #         print("null", end=' ')
    #     else:
    #         print(tree.val, end=' ')
    #         self.visit(tree.left)
    #         self.visit(tree.right)
    def generateTrees(self, n: int) -> List[TreeNode]:
        lis = [i+1 for i in range(n)]
        def build(lis, i, j):
            if i == j:
                return [TreeNode(lis[i])]
            elif i > j:
                return [None]
            res = []
            for k in range(i, j+1):
                leftTree = build(lis, i, k-1)
                rightTree = build(lis, k+1, j)
                for litem in leftTree:
                    for ritem in rightTree:
                        root = TreeNode(lis[k])
                        root.left = litem
                        root.right = ritem
                        res.append(root)
            return res
        return build(lis, 0, n-1)