给你一个整数 n ,请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

思路

  1. 遍历 1 ~ n
  2. 以 i 为根节点,1 ~ i - 1 为左子树,i + 1 ~ n 为右子树递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var generateTrees = function (n) {
const buildTrees = (vals) => {
if (vals.length === 0) {
return [null]
}
const trees = []
for (let i = 0; i < vals.length; ++i) {
const leftTrees = buildTrees(vals.slice(0, i))
const rightTrees = buildTrees(vals.slice(i + 1))
for (const left of leftTrees) {
for (const right of rightTrees) {
trees.push(new TreeNode(vals[i], left, right))
}
}
}
return trees
}
return buildTrees(new Array(n).fill(null).map((_, index) => index + 1))
}