给你一个整数 n ,请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
思路
遍历 1 ~ n
以 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(newArray(n).fill(null).map((_, index) => index + 1)) }