题意

给定一个整数 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)