力扣 95. 不同的二叉搜索树 II

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1、穷举root节点的所有可能。
2、递归构造出左右子树的所有合法 BST。
3、给root节点穷举所有左右子树的组合。

方法1：python

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        if n==0: return 

        def build(low,high):
            res=list()
            if low>high:
                res.append(None)
                return res

            #穷举所有根节点
            for i in range(low,high+1):
                #递归构造左右子树所有合法BST
                leftT=build(low,i-1)
                rightT=build(i+1,high)

                #组合左右子树
                for left in leftT:
                    for right in rightT:
                        #构造每一个根节点树
                        root=TreeNode(i)
                        root.left=left
                        root.right=right
                        res.append(root)
            return res
        return build(1,n)