1. 题目描述

给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。

示例:

输入: 3
输出:

[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]

解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：

 1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

2. 思路

这一题是上一题的扩展，思路大致相同，利用递归来构建左右子树。注意左子树和右子树的范围。

class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
if n == 0:
return []
return self.buildBst(1,n)
def buildBst(self,begin,end):
result = []
if end < begin:
result.append(None)
for i in range(begin,end+1):
for left in self.buildBst(begin,i-1):
for right in self.buildBst(i+1,end):
root = TreeNode(i)
root.left = left
root.right = right
result.append(root)
return result