题目描述

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

示例

示例 1：

输入: 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

解答方法

方法一：

思路

1.利用卡特兰数求解，G(n) = ∑i∈[0,n] G(i)G(n-i-1)
2.主要通过切点i,判断i的左右是否存在构成新的节点条件的值。
- 2.1 对于左边：是否存在x满足start<=x<i的值，如果存在则递归继续切分，继续判断，知道不满足返回[None]。
- 2.2 对于右边：是否存在x满足i<x<=end的值，如果存在则递归继续切分，继续判断，直到不满足返回[None]]。
3.通过for循环其实有着计算是个笛卡尔积的作用，leftright种可能。在循环中依次生成新的节点可能性，添加到all_trees列表中，
最后输出的列表将会包含所有中可能。因为该动态规划，采用自顶而下的方式。

注：这里用列表存储，因为继续切分得到的结果可能有多个，为了将这些结果合并，需采用for循环。
https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/bu-tong-de-er-cha-sou-suo-shu-ii-by-leetcode/

代码

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        def generate_tree(start, end):
            if start>end:
                return [None]
            all_trees = []
            for i in range(start,end+1):
                left_trees = generate_tree(start, i-1)
                right_trees = generate_tree(i+1, end)

                for l in left_trees:
                    for r in right_trees:
                        current_tree = TreeNode(i)
                        current_tree.left = l
                        current_tree.right = r
                        all_trees.append(current_tree)
            return all_trees
        
        if n:
            return generate_tree(1,n)
        else:
            return []