Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
分别选中1-n作为根节点，其左子树的节点们由[1,i-1]构成，右子树的节点们由[i+1,n]构成。
对于左子树和右子树继续递归
var generateTrees = function(n) {
function generate(start,end){
var subTree = [];
if(start > end){
subTree.push(null);
return subTree;
}
// i作为根节点
for(let i = start;i <= end;i++){
// 以i为根节点的树,其左子树由[start,i-1]构成,其右子树由[i+1,end]构成。
// 返回的是不同二叉查找树的根节点，几种二叉查找树就返回几个根节点
var leftSubTree = generate(start,i-1);
var rightSubTree = generate(i+1,end);
// 左子树右子树跟根节点连接
// 以i为根的树的个数，等于左子树的个数乘以右子树的个数
for(let j = 0;j < leftSubTree.length;j++){
for(let k = 0;k < rightSubTree.length;k++){
var node = new TreeNode(i);
node.left = leftSubTree[j];
node.right = rightSubTree[k];
subTree.push(node);
}
}
}
return subTree;
}
if (n===0) return [];
return generate(1,n);
};
