题目：
难度：Middle
相关话题：树、动态规划
给定一个整数 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
思路：
分而治之的思想，例如[1,5]这一段，根据BST的性质，可以分割成如下：
左 root 右
null 1 [2,5]
[1,1] 2 [3,5]
[1,2] 3 [4,5]
[1,3] 4 [5,5]
[1,4] 5 null
上面的左和右又可以按照同样的规则继续划分。
/**
* @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number} n
* @return {TreeNode[]}
*/
var generateTrees = function(n) {
if(n===0)return []
let result=[]
function cTree(left,right){
if(right<left)return [null]
// if(right===left)return [new TreeNode(left)]
let list=[]
for(let i=left;i<=right;i++){
let leftList=cTree(left,i-1)
let rightList=cTree(i+1,right)
for(let j=0;j<leftList.length;j++){
for(let k=0;k<rightList.length;k++){
let root=new TreeNode(i)
root.left=leftList[j]
root.right=rightList[k]
list.push(root)
}
}
}
return list
}
return cTree(1,n)
};