95. 不同的二叉搜索树 II
题意
给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
解题思路
这道题目是基于不同的二叉搜索树进行改进的；
对于连续整数序列[left, right]中的一点 i，若要生成以 i 为跟结点的BST，则有如下的规律：
i 左边的序列可以作为左子树结点，并且左儿子可能有多个，因此存在
left_nodes = self.helper(left, i-1)；i 右边的序列可以作为右子树结点，并且右儿子可能有多个，因此存在
right_nodes = self.helper(i+1, right)；产生的以当前结点 i 为跟结点的BST树有
len(left_nodes) * len(right_nodes)个，遍历每一种情况，即可以产生以 i 为跟结点的BST序列，因此以 for 循环使得[left, right]中每个结点都能生成子树序列；
一旦left大于right，则说明这里无法产生子树，所以此处应该是作为空结点返回；
实现
class Solution(object):
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n <= 0:
return []
return self.helper(1, n)
def helper(self, left, right):
result = []
# 一旦left大于right，则说明这里无法产生子树，所以此处应该是作为空结点返回
if left > right:
result.append(None)
return result
for i in range(left, right+1):
left_nodes = self.helper(left, i-1)
right_nodes = self.helper(i+1, right)
# 包括产生的以当前结点 i 为跟结点的BST树有len(left_nodes) * len(right_nodes)个，因此双层遍历
for left_node in left_nodes:
for right_node in right_nodes:
node = TreeNode(i)
node.left = left_node
node.right = right_node
result.append(node)
return result
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n <= 0:
return []
# 使用left，right表示左右两边结点对应个数的个数
result = defaultdict(list)
def helper(left, right):
if left > right:
return [None]
# 避免重复执行
if (left, right) in result:
return result[(left, right)]
for i in range(left, right+1):
left_nodes = helper(left, i-1)
right_nodes = helper(i+1, right)
# 包括产生的以当前结点 i 为跟结点的BST树有len(left_nodes) * len(right_nodes)个，因此双层遍历
for left_node in left_nodes:
for right_node in right_nodes:
node = TreeNode(i)
node.left = left_node
node.right = right_node
result[(left, right)].append(node)
return result[(left, right)]
return helper(1, n)