自己写了一个，但是结果每次总是和正确的差了一两个
现在给出官方解法 思路是 每次我们从[1,…,n]这个数组中取一个i作为root 则根据二叉搜索树的定义，[1,…,i-1]是左子树的候选集 [i+1,…,n] 对于i 假设我们从[1,…,i-1]中选择一个l作为i的左孩子 类似地，从[i+1,…,n]中选一个r作为i的右孩子 此时 将l和r放在i的下面，即完成了这两层的构建。 由于这种解法是使用递归的方法解决的本题 则首先下沉到最下面的两层 如何做到呢？ 即先递归左和右，再将递归得到的结果传给上一层 显然，如果使用i == 1 作为root 则其左孩子一定是空的 类似地，如果使用i==n作为root则其右孩子一定是空的 因此，需在构建两层的时候判断，是不是这种情况
class Solution: def generateTrees(self, n: int) -> List[TreeNode]: return self.generate_2_layer(1,n) if n != 0 else [] def generate_2_layer(self,start,end): all_trees = [] for i in range(start,end + 1): left_tree = self.generate_2_layer(start,i-1) if i > start else [None]#i==start right_tree = self.generate_2_layer(i+1,end) if i < end else [None]#i==end for l in left_tree: for r in right_tree: current_node = TreeNode(i) current_node.left = l current_node.right = r all_trees.append(current_node) return all_trees