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# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:defgenerateTrees(self,n:int)-List[Optional[TreeNode]]:ifn0:return[]returnself.build(1,n)defbuild(self,lo,hi):res[]iflohi:res.append(None)returnresforiinrange(lo,hi1):left_treeself.build(lo,i-1)right_treeself.build(i1,hi)forleftinleft_tree:forrightinright_tree:rootTreeNode(i)root.leftleft root.rightright res.append(root)returnres