给定一个整数 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
这一题是上一题的扩展,思路大致相同,利用递归来构建左右子树。注意左子树和右子树的范围。
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