Appearance
95. 不同的二叉搜索树 II
题目描述
给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树* *。可以按 任意顺序 返回答案。
示例 1：
**输入：**n = 3 输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
示例 2：
**输入：**n = 1 输出：[[1]]
提示：
1
难度： Medium
题解代码
javascript
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number} n
* @return {TreeNode[]}
*/
var generateTrees = function(n) {
return genTree(1, n)
};
function genTree (start, end) {
const allTrees = []
if (start > end) {
return [null]
}
// 枚举可行根节点
for (let i = start; i <= end; i++) {
// 获得所有可行的左子树集合
const leftTrees = genTree(start, i - 1);
// 获得所有可行的右子树集合
const rightTrees = genTree(i + 1, end);
for (let l = 0; l < leftTrees.length; l++) {
for(let r = 0; r < rightTrees.length; r++) {
const cur = new TreeNode(i, leftTrees[l], rightTrees[r])
allTrees.push(cur)
}
}
}
return allTrees;
}