給定n瑟俭，輸出所有的二叉搜索樹。
深度優(yōu)先搜索：要生成1～n構成的所有BST秀睛，生成1～k-1的BST作為左子樹尔当，以及k+1～n的所有BST作為右子樹，兩兩組合即可蹂安。當選擇的根節(jié)點的值比left小的時候椭迎，左子樹為空。
每次選取一個節(jié)點為根田盈，遞歸求解左右子樹的所有結果畜号，根據(jù)左右子樹返回所有子樹，依次選取接上允瞧，每個左邊的子樹跟所有右邊的子樹匹配简软，每個右邊子樹也要跟所有左邊的子樹匹配，總共有左右子樹數(shù)量的乘積種情況述暂，構造結束之后作為當前樹的結果返回痹升。
faster than 96%
/**
* 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) {
var tree = []
if(n === 0) return tree
dfs(1, n, tree)
return tree
};
var dfs = function(start, end, tree){
if(start > end){
tree.push(null)
return
}
for(var i = start; i <= end; i++){
var left = []
var right = []
dfs(start, i - 1, left)
dfs(i + 1, end, right)
for(var j = 0; j < left.length; j++){
for(var k = 0; k < right.length; k++){
var node = new TreeNode(i)
node.left = left[j]
node.right = right[k]
tree.push(node)
}
}
}
}
