Lstmxx的空间

95. 不同的二叉搜索树 II

给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。

链接

function generateTrees(n: number): Array<TreeNode | null> {
  if (!n) return []
  return traverse(1, n)
};

function traverse(inStart: number, inEnd: number): TreeNode[] {
  const result = []
  if (inStart > inEnd) {
    result.push(null)
    return result
  }
  for(let i = inStart; i <= inEnd; i++) {
    const left = traverse(inStart, i - 1)
    const right = traverse(i + 1, inEnd)
    const root = new TreeNode(i)
    const leftLen = left.length
    const rightLen = right.length
    for(let j = 0; j < leftLen; j++) {
      for(let k = 0; k < rightLen; k++) {
        const root = new TreeNode(i)
        root.left = left[j]
        root.right = right[k]
        result.push(root)
      }
    }
  }
  return result
}