给你一个整数 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))
}