Leetcode 95. 不同的二叉搜索树 II

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        def tree(i,j):
            if j==i:
                return [None]
            if j==i+1:
                return [TreeNode(i)]
            ret=[]
            for t in range(i,j):
                left,right=tree(i,t),tree(t+1,j)
                tmp=[]
                for lnode in left:
                    for rnode in right:
                        tnode=TreeNode(t)
                        tnode.left,tnode.right=lnode,rnode
                        tmp.append(tnode)
                ret.extend(tmp)
            return ret
        return [] if n==0 else tree(1,n+1)